home *** CD-ROM | disk | FTP | other *** search
/ Giga Games 1 / Giga Games.iso / net / go / comp / theory.sh < prev    next >
Encoding:
Linux/UNIX/POSIX Shell Script  |  1993-06-20  |  109.4 KB  |  3,801 lines
  1. #! /bin/sh
  2. # This is a shell archive, meaning:
  3. # 1. Remove everything above the #! /bin/sh line.
  4. # 2. Save the resulting text in a file.
  5. # 3. Execute the file with /bin/sh (not csh) to create:
  6. #    HELP
  7. #    Makefile
  8. #    README
  9. #    bitmatrix.c
  10. #    bitmatrix.h
  11. #    corridors.c
  12. #    corridors.h
  13. #    domino.c
  14. #    domino.h
  15. #    externs.h
  16. #    games.c
  17. #    grammar.y
  18. #    hash.c
  19. #    hash.h
  20. #    list.c
  21. #    list.h
  22. #    main.c
  23. #    operations.c
  24. #    operations.h
  25. #    output.c
  26. #    output.h
  27. #    parse.l
  28. #    rational.c
  29. #    rational.h
  30. # This archive created: Sun Oct  6 20:23:54 1991
  31. export PATH; PATH=/bin:/usr/bin:$PATH
  32. if test -f 'HELP'
  33. then
  34.     echo shar: "will not over-write existing file 'HELP'"
  35. else
  36. cat << \SHAR_EOF > 'HELP'
  37.   Run without arguments, the games program executes each argument as
  38.   a command line, and then exits.  For instance, typing
  39.      games evaluate tex "2||1|*"
  40.   will output
  41.      1 \int{ 1\over 4}
  42.  
  43.   Things enclosed in []'s are subscripts and things in <>'s are superscripts.
  44. ---------------------------------------------------------
  45. 7/2            G -> Q | N        numbers         | N integer
  46. ^3            G -> ^N | ^        up (v is down)     | G game
  47. *5            G -> *N | *        star         | L list
  48. +[2]            G -> +[G]        tiny (- is miny) | Q rational
  49.                                  | V variable
  50. {^3}            G -> {G} | (G)        (same for L's)     --------------
  51. 3||2|1            G -> L '|' L        3 vs (2 vs 1)   
  52. 3,{4|2}|1        L -> G | G,L        {3,{4|2}}|1    
  53.                                 
  54. 3+2            G -> G + G | G - G    add/subtract    
  55. (3|2)[1/4]        G -> G[Q]        cool G by Q
  56. (3|2)[]            G -> G[]        apply chill-function to G
  57. mean (3|2)        Q -> mean G        mean
  58. temperature (3|2)    Q -> temperature G    temperature
  59. freeeze (3|2)        G -> freeze G        cool by temperature
  60. %[1*]<1>(3|2)        G -> %[G]<G>G        overheating
  61. %(3|2)            G -> %G            apply warm-function to G
  62. +[3]<3>            G -> G<N>        generalization of up^n
  63. [+[3]]<(3)>        G -> on G <N>        generalization of upon
  64. 0<3>|+[3]        G -> 0<n> '|' G        0|||0||0|G
  65. ^3.1*            G -> G.G        Norton multiply 
  66. aw (0|+[1])        G -> aw G        atomic weight
  67. 1 ? *              -> G ? G        compare games (<, >, =, or <>)
  68.  
  69. x            G -> G            get variable's value
  70. vAr7=2            G -> V=G        set variable
  71.             V -> [a-zA-Z]+[0-9]*    variable starts with character
  72.  
  73. corridor (1u2(b3))    G -> corridor...    invading corridors in go
  74. domino            G -> domino <cr> ...    evaluate a domineering position
  75. chill g[1]          -> chill f(g)        set chilling function (for evaluate)
  76. warm g.1*          -> warm f(g)        set warming funcion (for evaluate)
  77. K            G -> "K" | "k"        K = 1 point ko, k = chilled K
  78.  
  79. -- PRINT OPTIONS --
  80. no (option)    Cancel option
  81. integers    Recognize canonical forms of integers
  82. numbers
  83. stars
  84. ups
  85. tinys
  86. ons
  87. variables    Substitute variable names for games
  88. expand        If outputing a game identical to a variable, give both
  89. prompt        Give prompt of "> "
  90. all        All of the above options are set
  91. evaluate    Tries to chill and warm back up
  92. normalize    With evaluate, normalizes the result to n%g (default's to on)
  93. assume        Make unproven assumptions about go positions for efficiency
  94. assume2        Make false assumptions about go -- size of captured group ignored
  95. echo        Echo input line back
  96. clean        Clean out hash table after every command - saves space
  97. tex        Output all formulas in TeX.  TeX macros \neg, \Up, \Upup,
  98.                   \Down, \Downdown, \UpN{n}, \DownN{n}, \Star, \Tiny{G}, \Miny{G}
  99.           are used, and should be defined by your TeX.
  100. stat        Give hash table and list statistics - (debugging tool)
  101. SHAR_EOF
  102. fi
  103. if test -f 'Makefile'
  104. then
  105.     echo shar: "will not over-write existing file 'Makefile'"
  106. else
  107. cat << \SHAR_EOF > 'Makefile'
  108. # Copyright (C) David Wolfe, 1990.  All rights reserved.
  109.  
  110. CFLAGS =
  111. OBJ = hash.o list.o operations.o output.o rational.o grammar.o corridors.o domino.o bitmatrix.o
  112. CC = gcc
  113. CFLAGS_ = -g
  114. CFLAGS = $(CFLAGS_) -Wall
  115. YFLAGS =
  116. CFILES = rational.c list.c hash.c operations.c output.c games.c main.c corridors.c domino.c bitmatrix.c
  117. HFILES = externs.h rational.h list.h hash.h operations.h output.h corridors.h domino.h bitmatrix.h
  118. ALL = $(CFILES) $(HFILES) HELP Makefile README grammar.y parse.l
  119.  
  120. all: games
  121.  
  122. tags:
  123.     etags $(CFILES) $(HFILES) grammar.y parse.l
  124.  
  125. bundle: $(ALL)
  126.     rm -f .bundle
  127.     bundle $(ALL) > .bundle
  128.  
  129. games: $(OBJ) Makefile main.o
  130.     $(CC) $(CFLAGS) -o games $(OBJ) main.o
  131.  
  132. ibm: ibm.c
  133.     gcc ibm.c -o ibm
  134.  
  135. ibm.c: Makefile $(HFILES) $(CFILES)
  136.     rm -f ibm.c
  137.     echo "#include <stdio.h>" > ibm.c
  138.     cat $(HFILES) $(CFILES) | grep -v "include" >> ibm.c
  139.     awk "/parse.c/ {exit}; {print}" grammar.c | grep -v "include" >> ibm.c
  140.     cat parse.c | grep -v "include" >> ibm.c
  141.     awk "a==1 {print}; /parse.c/ {a=1}" grammar.c | grep -v "include" >> ibm.c
  142.  
  143. .y.o:
  144.     $(YACC) $(YFLAGS) $<
  145.     $(CC) $(CFLAGS) -c y.tab.c
  146.     'mv' y.tab.c $*.c
  147.     'mv' y.tab.o $@
  148.  
  149. grammar.o: parse.c externs.h rational.h list.h operations.h output.h corridors.h domino.h
  150.     $(CC) $(CFLAGS_) -c grammar.c
  151.  
  152. parse.c: parse.l
  153. grammar.c: grammar.y parse.c
  154. hash.o: externs.h list.h hash.h
  155. list.o: externs.h list.h
  156. operations.o: externs.h rational.h hash.h list.h operations.h output.h
  157. output.o: externs.h rational.h list.h operations.h output.h
  158. rational.o: externs.h rational.h
  159. main.o: externs.h rational.h list.h hash.h operations.h output.h games.c
  160. corridors.o: externs.h list.h hash.h rational.h operations.h corridors.h output.h
  161. domino.o: externs.h list.h hash.h rational.h operations.h domino.h bitmatrix.h
  162. bitmatrix.o: bitmatrix.h bitmatrix.c
  163. SHAR_EOF
  164. fi
  165. if test -f 'README'
  166. then
  167.     echo shar: "will not over-write existing file 'README'"
  168. else
  169. cat << \SHAR_EOF > 'README'
  170. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  171.  
  172.         David Wolfe's games program summary
  173.  
  174. This code implements most of combinatorial game theory found in
  175. Winning Ways, and other references are listed at the end of this file.
  176.  
  177. My electronic mail address is wolfe@mandolin.Berkeley.EDU, if you want
  178. a copy to install.  To run, type "games", and at the prompt simply
  179. type in most reasonable formats for games you've seen.  The most
  180. unusual format is +[3] which is "tiny 3".  You can assign and use
  181. variables, including in the middle of partial results.  For example,
  182. "a = +[b=4]" sets a to +[4] and b to 4.  Also, you have some control
  183. over what is recognized as canonical form for output.  For instance,
  184. if you type the command "no tinys", then +[2] will get printed out as
  185. "0||0|-2".  (By default it tries to recognize as much as possible.)
  186. Variables you've assigned at one stage show up later in other games'
  187. canonical forms.  "no variables" turns this option off.
  188.  
  189. For example:
  190. a=2|1     outputs a = 2|1
  191. b=3||2|1 outputs b = 3|a
  192.  
  193. ----------------------------------------------------------------
  194. PLEASE let me know of comments/bugs/suggestions/etc.
  195. ----------------------------------------------------------------
  196. Installation:
  197.  
  198. Set variables in externs.h if you want the help command to work.
  199.  
  200. type "make".  If you're using ansi-C, you might want to remove
  201. the commented out type declarations in the .h files for
  202. debugging.
  203.  
  204. HELP for semi-complete summary of commands.  TODO for improvements
  205. likely to be done.  Again, please mail me suggestions that you'd like
  206. to see beyond what in the TODO file.
  207. ----------------
  208. Combinatoric Game Theory references:
  209.  
  210. Winning Ways, Elwyn R. Berlekamp and John H. Conway and Richard K.
  211. Guy, Academic Press, New York, 1982.
  212.  
  213. Blockbusting and Domineering, Elwyn R. Berlekamp, Journal of
  214. Combinatorial Theory, 1988, Vol 49, No 1, Series A, September 1988.
  215.  
  216. On Numbers and Games, John H. Conway, Academic Press, London/New York, 1976.
  217.  
  218. SHAR_EOF
  219. fi
  220. if test -f 'bitmatrix.c'
  221. then
  222.     echo shar: "will not over-write existing file 'bitmatrix.c'"
  223. else
  224. cat << \SHAR_EOF > 'bitmatrix.c'
  225. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  226.  
  227. #include "externs.h"
  228. #include "list.h"
  229. #include "bitmatrix.h"
  230.  
  231. B_type B_make (int x, int y)
  232. {
  233.     B_type a;
  234.     int i;
  235.  
  236.     if (!(a = (B_type) malloc (sizeof (struct B_struct))))
  237.         myerror ("B_make: malloc couldn't free block");
  238.     a->x = x;
  239.     a->y = y;
  240.     if (!(a->contents = (unsigned *) malloc (((x*y+(INT_SIZE - 1)) / INT_SIZE) * sizeof (unsigned))))
  241.         myerror ("B_make: malloc couldn't free block");
  242.     for (i = 0; i < (x*y+(INT_SIZE - 1))/INT_SIZE; i++) *(a->contents + i) = (unsigned) 0;
  243.     return a;
  244. }
  245.  
  246. list_type B_to_list (B_type a)
  247. {
  248.     list_type l;
  249.     int i;
  250.     
  251.     l = list_make();
  252.     list_insert_unsorted (l, a->x);
  253.     list_insert_unsorted (l, a->y);
  254.     for (i = 0; i <= (a->x * a->y) / INT_SIZE; i++) list_insert_unsorted (l, *(a->contents + i));
  255.     return l;
  256. }
  257.  
  258. B_type B_pack (B_type a)
  259. {
  260.     B_type b;
  261.     int i, j, xmin, ymin, xmax, ymax;
  262.  
  263.     xmin=a->x, ymin=a->y, xmax=-1, ymax=-1;
  264.     for (i=0; i < a->x; i++)
  265.         for (j=0; j < a->y; j++)
  266.             if (B_get (a,i,j)) {
  267.                 if (i < xmin) xmin = i;
  268.                 if (j < ymin) ymin = j;
  269.                 if (i > xmax) xmax = i;
  270.                 if (j > ymax) ymax = j;
  271.             }
  272.     if (xmin == 0 && ymin==0 && xmax==a->x-1 && ymax==a->y-1) return a;
  273.     if (xmin > xmax) {
  274.         B_free (a);
  275.         return B_make (0,0);
  276.     }
  277.     b = B_make (xmax - xmin + 1, ymax - ymin + 1);
  278.     for (i = 0; i < xmax - xmin + 1; i++)
  279.         for (j = 0; j < ymax - ymin + 1; j++)
  280.             if (B_get (a, i+xmin, j+ymin)) B_set (b,i,j);
  281.     B_free (a);
  282.     return b;
  283. }
  284.  
  285. void B_printf (B_type a) {
  286.     int x,y;
  287.     for (x = 0; x < a->x; x++) {
  288.         for (y = 0; y < a->y; y++)
  289.             printf ("%d", B_get (a,x,y) ? 1 : 0);
  290.         printf ("\n");
  291.     }
  292. }
  293. SHAR_EOF
  294. fi
  295. if test -f 'bitmatrix.h'
  296. then
  297.     echo shar: "will not over-write existing file 'bitmatrix.h'"
  298. else
  299. cat << \SHAR_EOF > 'bitmatrix.h'
  300. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  301.  
  302. /* Maintains an 2 dimensional bit array */
  303.  
  304. typedef struct B_struct {
  305.     int x;
  306.     int y;
  307.     unsigned *contents;
  308. } *B_type;
  309.  
  310. #define SpOt(a,i,j) ((i) * (a)->y + (j))
  311. #define ByTe(a,i,j) ((a)->contents + (SpOt(a,i,j) / INT_SIZE))
  312. #define BiT(a,i,j) (SpOt(a,i,j) % INT_SIZE)
  313.  
  314. #define B_get(a,i,j)   ((*ByTe(a,i,j) &   (1<<BiT(a,i,j))) != 0)
  315. #define B_set(a,i,j)   ( *ByTe(a,i,j) |=  (1<<BiT(a,i,j)))
  316. #define B_clear(a,i,j) ( *ByTe(a,i,j) &= ~(1<<BiT(a,i,j)))
  317. #define B_free(a) (free ((a)->contents), free (a))
  318. #define B_x(a) ((a)->x)
  319. #define B_y(a) ((a)->y)
  320.  
  321. extern B_type            B_make (int, int);
  322. extern list_type        B_to_list (B_type);
  323. extern B_type            B_pack (B_type);
  324. extern void            B_printf (B_type);
  325. SHAR_EOF
  326. fi
  327. if test -f 'corridors.c'
  328. then
  329.     echo shar: "will not over-write existing file 'corridors.c'"
  330. else
  331. cat << \SHAR_EOF > 'corridors.c'
  332. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  333.  
  334. /* if (flags & ASSUME_FLAG) is true,
  335.  * We assume that 1) players want to invade/block ONLY the longest
  336.  * blocked or unblocked corridor of a given group.  2) White's
  337.  * invasion of an unblocked corridor is REVERSED throught the blck of
  338.  * that same corridor. */
  339.  
  340. #include "externs.h"
  341. #include "list.h"
  342. #include "hash.h"
  343. #include "rational.h"
  344. #include "operations.h"
  345. #include "corridors.h"
  346. #include "output.h"
  347.  
  348. list_type invasion [MAX_INVASIONS];
  349. #ifdef IBMPC
  350. unsigned invasions=0;
  351. #else
  352. unsigned long invasions=0;
  353. #endif
  354. int change_sizes = 1; /* "1/0" means assume size of invading groups "do/don't" matter */
  355.  
  356. extern void corridor_Print();
  357.  
  358. void corridor_clear(void) {
  359.     unsigned long i;
  360.     
  361.     for (i = 1; i <= invasions; i++)
  362.         list_free (invasion[i]);
  363.     invasions = 0;
  364. }
  365.  
  366. game_type blocked (int n) {
  367.     return plus (g_int (n-2), mult (num (Q_exp (1-n)), one_star));
  368. }
  369.  
  370. game_type unblocked (int n) {
  371.     if (n == 0) return zero;
  372.     else if (n == 1) return star (1);
  373.     else return plus (g_int (n-4), mult (num (Q_exp (3-n)), one_star));
  374. }
  375.  
  376. int corridor_get (list_type l) {
  377.     if (hash_test (CORRIDOR_KEY, l)) return hash_get_last ();
  378.     if (++invasions >= MAX_INVASIONS) {
  379.         myerror ("corridor_get: No more invasions.  Sorry.");
  380.         exit (1);
  381.     }
  382.     invasion[invasions] = list_copy (l);
  383.     hash_put (CORRIDOR_KEY, list_copy (l), invasions);
  384.     return invasions;
  385. }
  386.  
  387. static int corridor_size (int i) {
  388.     list_type l;
  389.  
  390.     for (l = list_start (invasion[i]); l != NIL; l = list_rest (l))
  391.         if ((FLAGS & list_pick (l)) == SIZE)
  392.             return (list_pick (l) & DATA);
  393.     myerror ("corridor_size: No Size");
  394.     return 0;
  395. }
  396.  
  397. static int corridor_change (int stack[], int o1, int o2, int n1, int n2) {
  398.     list_type inv;
  399.     int i,j;
  400.  
  401.     inv = invasion[i = stack[stack[0]]];
  402.     if (o1 != 0) list_delete (inv, o1);
  403.     if (o2 != 0) list_delete (inv, o2);
  404.     if (n1 != 0) list_insert (inv, n1);
  405.     if (n2 != 0) list_insert (inv, n2);
  406.     j = corridor_get (inv);
  407.     if (n1 != 0) list_delete (inv, n1);
  408.     if (n2 != 0) list_delete (inv, n2);
  409.     if (o1 != 0) list_insert (inv, o1);
  410.     if (o2 != 0) list_insert (inv, o2);
  411.     if (stack[0] > 1) {
  412.         stack[0]--;
  413.         j = corridor_change (stack, FOLLOWER|i, 0, FOLLOWER|j, 0);
  414.         stack[0]++;
  415.     }
  416.     return j;
  417. }
  418.  
  419. /* An invasion is a list encoding size, parent, blocked, unblocked, follower */
  420. /* Function used to construct left and right followers */
  421. static void corridor_eval (int i, int stack[], list_type left, list_type right) {
  422.     int size, parent=0, long_b=0, long_u=0, followers=0;
  423.     list_type inv, l, l1, l2;
  424.     int n, flgs, data, t;
  425.     game_type g;
  426.  
  427.     if (stack[0] != 1) parent = stack[stack[0]-1];
  428.     inv = list_copy (invasion [i]);
  429.     for (l = list_start (inv); l != NIL; l = list_rest (l)) {
  430.         n = list_pick (l);
  431.         flgs = n & FLAGS;
  432.         data = n & DATA;
  433.         if (flgs == SIZE) size = data;
  434.         else if (flgs == BLOCKED && (data > long_b)) long_b = data;
  435.         else if (flgs == UNBLOCKED && (data > long_u)) long_u = data;
  436.         else if (flgs == FOLLOWER) { /* move on child */
  437.             followers++;
  438.             stack[++stack[0]] = data;
  439.             corridor_eval (data, stack, left, right);
  440.             stack[0]--;
  441.         }
  442.     }
  443.     /* black captures */
  444.     if (long_b + long_u + followers == 0) {
  445.         if (parent != 0) {
  446.             stack[0]--;
  447.             g = corridor_val (corridor_change (stack, FOLLOWER|i,0,0,0));
  448.             stack[0]++;
  449.         }
  450.         else
  451.             g = zero;
  452.         list_insert (left, plus (g, g_int (2 * size)));
  453.     }
  454.     /* white connects to parent*/
  455.     if (parent != 0) {
  456.         l1 = list_copy (inv);
  457.         l2 = list_copy (invasion [parent]);
  458.         list_delete (l1, SIZE | size);
  459.         t = corridor_size (parent);
  460.         if (! (flags & ASSUME2_FLAG)) {
  461.             list_delete (l2, SIZE | t);
  462.             list_insert (l2, SIZE | (t + size + 1));
  463.         }
  464.         list_delete (l2, FOLLOWER | i);
  465.         t = corridor_get (l = list_multi_union (l1, l2));
  466.         if (stack[0] > 2) {
  467.             stack[0] -= 2;
  468.             t = corridor_change (stack, FOLLOWER|stack[stack[0]+1],0,FOLLOWER|t,0);
  469.             stack[0] += 2;
  470.         }
  471.         list_insert (right, corridor_val (t));
  472.         list_free (l);
  473.         list_free (l1);
  474.         list_free (l2);
  475.     } else {
  476.         g = zero;
  477.         for (l = list_start (inv); l != NIL; l = list_rest (l)) {
  478.             n = list_pick (l);
  479.             flgs = FLAGS & n;
  480.             data = DATA & n;
  481.             if (flgs == BLOCKED) g = plus (g, blocked (data));
  482.             else if (flgs == UNBLOCKED) g = plus (g, unblocked (data));
  483.             else if (flgs == FOLLOWER) g = plus (g, corridor_val (data));
  484.         }
  485.         list_insert (right, g);
  486.     }
  487.     list_free (inv);
  488.     if (long_b > 0) {
  489.         /* black blocks longest blocked */
  490.         list_insert (left, plus (g_int (long_b - 1), corridor_val (corridor_change (stack,long_b|BLOCKED,0,0,0))));
  491.         /* white invades longest blocked */
  492.         list_insert (right, corridor_val (corridor_change (stack, long_b|BLOCKED, size|SIZE,long_b==1? 0 : BLOCKED|(long_b-1),
  493.                              (size+(flags & ASSUME2_FLAG ? 0 : 1))|SIZE)));
  494.     }
  495.     if (long_u == 1) myerror ("Corridor_eval: Unblocked corridor length 1");
  496.     else if (long_u > 1) {
  497.         /* black blocks longest unblocked */
  498.         list_insert (left, plus (blocked (long_u-1), corridor_val (corridor_change (stack,UNBLOCKED|long_u,0,0,0))));
  499.         if (! (flags & ASSUME_FLAG)) /* This move should be dominated ?? */
  500.             list_insert (left, corridor_val (corridor_change (stack, UNBLOCKED|long_u, 0, BLOCKED|(long_u-1), 0)));
  501.         /* white invades longest unblocked */
  502.         if ((flags & ASSUME_FLAG) || (long_u == 2)) {
  503.             /* Here we assume move reverses */
  504.             g = plus (corridor_val (corridor_change (stack, UNBLOCKED|long_u,0,0,0)), blocked (long_u-2));
  505.             for (l = list_start (right_options (g)); l!=NIL; l=list_rest (l))
  506.                 list_insert (right, list_pick (l));
  507.         } else
  508.             list_insert (right, corridor_val (corridor_change (stack, UNBLOCKED|long_u, 0, UNBLOCKED|(long_u-1), 0)));
  509.     }
  510.     return;
  511. }
  512.  
  513. game_type corridor_val (int i) {
  514.     list_type left, right;
  515.     int stack[MAX_DEPTH];
  516.     game_type g;
  517.  
  518.     if (hash_test (CORRIDOR_VALUE_KEY, list_1 (i))) return hash_get_last();
  519.     stack[0] = 1;
  520.     stack[1] = i;
  521.     left = list_make();
  522.     right = list_make();
  523.     corridor_eval (i, stack, left, right);
  524.     g = make (left, right);
  525.     hash_put (CORRIDOR_VALUE_KEY, list_copy_1 (i), g);
  526.     return g;
  527. }
  528.  
  529. void corridor_Print (int i) {
  530.     int n, data, flgs;
  531.     list_type l;
  532.     printf ("(");
  533.     for (l = list_start (invasion[i]); l != NIL; l = list_rest (l)) {
  534.         n = list_pick (l);
  535.         flgs = n & FLAGS;
  536.         data = n & DATA;
  537.         if (flgs == SIZE) printf ("%d", data);
  538.         else if (flgs == BLOCKED) printf ("b%d", data);
  539.         else if (flgs == UNBLOCKED) printf ("u%d", data);
  540.         else if (flgs == FOLLOWER) corridor_Print (data);
  541.     }
  542.     printf (")");
  543. }
  544.  
  545. void corridor_printf (int i) {
  546.     corridor_Print (i);
  547.     printf ("\n");
  548. }
  549.  
  550. int corridor_stat (void) {
  551.     unsigned long i,n=0;
  552.     
  553.     for (i = 1; i <= invasions; i++)
  554.         n = n + list_length (invasion[i]) + 1;
  555.     printf ("corridors: %d\n", n);
  556.     return n;
  557. }
  558. SHAR_EOF
  559. fi
  560. if test -f 'corridors.h'
  561. then
  562.     echo shar: "will not over-write existing file 'corridors.h'"
  563. else
  564. cat << \SHAR_EOF > 'corridors.h'
  565. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  566.  
  567. /* Uses games package to compute values of corridors in go.  A
  568.    position represents a (white) tree of invading groups, each of
  569.    which needs one move to connect to its parent, whose other
  570.    liberties are (black) "blocked" and "unblocked" corridors of
  571.    territory. -- Best expained by example. */
  572.  
  573. /*
  574.   ....|.|
  575.   ...XXXO...
  576.   ...X.X.X|.
  577.   |..X.X.XX.
  578.   OOOX.XOOXX
  579.   O..OOO.O.X
  580. */
  581.  
  582. /* Here every group with a | next to it is alive (immortal).  There
  583.    are two white invading groups:  The first is 3 stones attacking a
  584.    "blocked" corridor of length 3 and needs one move to connect to
  585.    life.  The second is 3 stones attacking an "unblocked" corridor of
  586.    length 2 and a "blocked" corridor of length 1, and needs one move
  587.    to connect to the first invading group. */
  588.  
  589. /* The input format for this position is
  590.    corridor (3b3 (3b1u2))
  591.    In general, there is a left paren, followed by the size of a
  592.    group followed by a list of liberties, followed by a close paren.
  593.    Each liberty can either be a blocked corridor -- a "b" followed by
  594.    a length, or an unblocked (u), or another invading group which
  595.    needs to connect to the current ((3b1u2) in the current example).
  596.    */
  597.  
  598. extern int corridor_get(list_type);
  599. extern game_type corridor_val(int);
  600. extern void corridor_printf (int);
  601. extern void corridor_clear (void);
  602.  
  603. #define F1        (1<<(INT_SIZE-1))
  604. #define F0        (1<<(INT_SIZE-2))
  605. #define FLAGS        (F0 | F1)
  606. #define SIZE        (0)
  607. #define BLOCKED        (F0)
  608. #define UNBLOCKED    (F1 | F0)
  609. #define FOLLOWER    (F1)
  610. #define DATA        (F0 - 1)
  611. #define MAX_DEPTH 10
  612. #define MAX_INVASIONS (MAX_SIZE < DATA ? MAX_SIZE : DATA)
  613. SHAR_EOF
  614. fi
  615. if test -f 'domino.c'
  616. then
  617.     echo shar: "will not over-write existing file 'domino.c'"
  618. else
  619. cat << \SHAR_EOF > 'domino.c'
  620. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  621.  
  622. #include <stdio.h>
  623. #include "externs.h"
  624. #include "list.h"
  625. #include "hash.h"
  626. #include "rational.h"
  627. #include "operations.h"
  628. #include "output.h"
  629. #include "bitmatrix.h"
  630. #include "domino.h"
  631.  
  632. /* Don't forget to free up space */
  633.  
  634. game_type place_domino (B_type, int, int, int, int);
  635. void copy_connected_component_at (B_type, B_type, int, int);
  636.  
  637. game_type domino_position (B_type pos)
  638. {
  639.     game_type g;
  640.     int i, j;
  641.     list_type left, right, l;
  642.     
  643.     left=list_make();
  644.     right=list_make();
  645.     l = B_to_list (pos);
  646.     if (hash_test (DOMINO_KEY, l)) return list_free (l), hash_get_last();
  647.     for (i = 0; i < B_x(pos); i++)
  648.         for (j = 0; j < B_y(pos); j++)
  649.             if (B_get (pos, i, j)) {
  650.                 if ((i+1 < B_x(pos)) && B_get(pos, i+1, j))
  651.                     list_insert (right, place_domino (pos, i,j, i+1,j));
  652.                 if ((j+1 < B_y(pos)) && B_get(pos, i, j+1))
  653.                     list_insert (left, place_domino (pos, i,j, i,j+1));
  654.             }
  655.     g = make (left, right);
  656.     hash_put (DOMINO_KEY, l, g);
  657.     return g;
  658. }
  659.  
  660. game_type place_domino (B_type pos, int x1, int y1, int x2, int y2)
  661. {
  662.     game_type g;
  663.     B_type new, old;
  664.     int i, j;
  665.     boolean done_something;
  666.  
  667.     g = zero;
  668.     old = B_make (B_x(pos), B_y(pos));
  669.     for (i = 0; i < B_x(old); i++)
  670.         for (j = 0; j < B_y(old); j++)
  671.             if (B_get (pos,i,j)) B_set (old,i,j);
  672.     B_clear (old, x1, y1);
  673.     B_clear (old, x2, y2);
  674.     for (done_something=TRUE;done_something;) {
  675.         done_something=FALSE;
  676.         for (j = 0; j < B_y(old); j++)
  677.             for (i = 0; i < B_x(old); i++)
  678.                 if (B_get (old, i, j)) {
  679.                     new = B_make(B_x(old),B_y(old));
  680.                     copy_connected_component_at (old, new, i, j);
  681.                     new = B_pack (new);
  682.                     g = plus (g, domino_position (new));
  683.                     B_free (new);
  684.                     done_something = TRUE;
  685.                 }
  686.     }
  687.     B_free (old);
  688.     return g;
  689. }
  690.  
  691. int pos_x[]={1,0,-1,0};
  692. int pos_y[]={0,1,0,-1};
  693. void copy_connected_component_at (B_type old, B_type new, int x, int y)
  694. {
  695.     int i,j,n;
  696.  
  697.     B_clear (old, x, y);
  698.     B_set (new, x, y);
  699.     for (n = 0; n <= 3; n++) {
  700.         i = x + pos_x[n];
  701.         j = y + pos_y[n];
  702.         if (i >= 0 && j >= 0 && i < B_x(old) && j < B_y(old) && B_get (old,i,j))
  703.             copy_connected_component_at (old, new, i, j);
  704.     }
  705. }
  706.  
  707. B_type input_domino(void)
  708. {
  709.     B_type pos;
  710.     char s[MAXBUFF];
  711.     int i=0, j;
  712.     
  713.     pos = B_make(DOMINO_INPUT_SIZE,DOMINO_INPUT_SIZE);
  714.     printf ("Enter domineering position followed by extra <cr>\n");
  715.     for (j=0; gets(s) != NULL && *s != '\0';j++) {
  716.         for (i=0; *(s+i) != '\0'; i++)
  717.             if (*(s+i) != ' ') B_set (pos, i, j);
  718.     }
  719.     if (j==0 && i==0) return (B_type) NULL;
  720.     else return B_pack(pos);
  721. }
  722.  
  723. static int dc_x (int x, int y, int i) {
  724.     int m, n;
  725.     if (x == 0) { /* domineering chain hardwired: over : 3x4x3x3 */  
  726.         n = i%9;
  727.         return n <= 2 ? n :
  728.                n <= 5 ? 2 :
  729.                n <= 7 ? 7-n :
  730.                     0;
  731.     }
  732.     m = i/(x+y-2);
  733.     n = i%(x+y-2);
  734.     if (n<x-1) return (x-1)*m + n;
  735.     else return (x-1)*(m+1);
  736. }
  737.  
  738. static int dc_y (int x, int y, int i) {
  739.     int m, n;
  740.     if (x == 0) {
  741.         m = i/9;
  742.         n = i%9;
  743.         return n <= 2 ? m*5 :
  744.                n <= 5 ? m*5 + n-2 :
  745.                n <= 7 ? m*5 + 3 :
  746.                     m*5 + n-4;
  747.     }
  748.     m = i/(x+y-2);
  749.     n = i%(x+y-2);
  750.     if (n<x-1) return (y-1)*m;
  751.     else return (y-1)*m + (n-(x-1));
  752. }
  753. #define X(i) dc_x (x,y,(i))
  754. #define Y(i) dc_y (x,y,(i))
  755. game_type domino_chain (int x, int y, int from, int to) {
  756.     B_type a;
  757.     int i, fx, fy;
  758.     game_type g;
  759.  
  760.     if (to <= from) return zero;
  761.     fx = (x==0 ? 0 : X(from));
  762.     fy = Y(from);
  763.     a = B_make (x == 0 ? 3 : X(to)-fx+1, Y(to)-fy+1);
  764.     for (i = from; i <= to; i++)
  765.         B_set (a, X(i)-fx, Y(i)-fy);
  766.     g = domino_position (a);
  767.     B_free (a);
  768.     return g;
  769. }
  770.     
  771. game_type domino (list_type l)
  772. {
  773.     int x, y, from, to, length, last, width;
  774.     B_type pos;
  775.     char s[MAXBUFF];
  776.     game_type g;
  777.     
  778.     length = list_length (l);
  779.     if (length == 0) {
  780.         pos = input_domino();
  781.         g = domino_position (pos);
  782.         B_free (pos);
  783.         return g;
  784.     }
  785.     if (length == 1) {
  786.         myerror ("Domineering position with 1 arg");
  787.         return NO_GAME;
  788.     }
  789.     last=0;
  790.     x = list_nth (l, 1);
  791.     y = list_nth (l, 2);
  792.     if (length == 2) {
  793.         width = (x == 0 ? 9 : x+y-2);
  794.         printf ("\n%dx%d domineering chain - period %d, saltus %s", x, y, period, game_sprintn (s,saltus, 20));
  795.         if (flags & EVALUATE_FLAG) printf (", warming function: %s", warm_string);
  796.         else printf ("\n");
  797.         printf ("%3s |",""); for (from=0; from < width; from++) printf (" %8", from+1); printf ("\n");
  798.         printf ("---------------------------------------------------------------------------------------\n");
  799.         for (to=0; (to <= last*3 || to <= 10) && to <= 200; to++) {
  800.             printf ("%3d |", to+1);
  801.             for (from=0; from < width; from++) {
  802.                 g = domino_chain (x,y,from,to);
  803.                 if (to>period && eq (g, plus (domino_chain (x,y,from,to-period), saltus)))
  804.                     *s='\0';
  805.                 else {
  806.                     game_sprintn (s, g, MAXBUFF);
  807.                     last = to;
  808.                 } printf (" %8s", s);
  809.             }
  810.             printf ("\n");
  811.             fflush (stdout);
  812.         }
  813.         return NO_GAME;
  814.     }
  815.     from = list_nth (l, 3);
  816.     if (length == 3) {
  817.         printf ("%3s |  %d by %d domineering chain starting with the %d'th square\n", " ", x, y, from);
  818.         printf ("---------------------------------------------------------------------------------------\n");
  819.         from--;
  820.         for (to=0; (to<=last*3 || to<=10) && to < 100; to++) {
  821.             g = domino_chain (x,y,from,to);
  822.             if (to>period && eq (g, plus (domino_chain (x,y,from,to-period), saltus))) *s = '\0';
  823.             else game_sprintn (s, g, MAXBUFF), last=to;
  824.             printf ("%3d | %s", to+1, s);
  825.             printf ("\n");
  826.             fflush (stdout);
  827.         }
  828.         return NO_GAME;
  829.     }
  830.     to = list_nth (l, 4);
  831.     if (length == 4)
  832.         return domino_chain (x,y,from,to);
  833.     myerror ("domino with more than 4 arguments");
  834.     return NO_GAME;
  835. }
  836. SHAR_EOF
  837. fi
  838. if test -f 'domino.h'
  839. then
  840.     echo shar: "will not over-write existing file 'domino.h'"
  841. else
  842. cat << \SHAR_EOF > 'domino.h'
  843. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  844.  
  845. /* Evaluates domineering positions:
  846.    for example, the position
  847. X
  848. X
  849. XX
  850.   is worth 1/2, and is also represented as the chain
  851.   x=3, y=2, from=1, to=4.
  852. */
  853. #define DOMINO_INPUT_SIZE 20
  854.  
  855. extern game_type    domino (list_type);
  856. extern game_type    domino_position (B_type);
  857. extern B_type        input_domino(void);
  858. SHAR_EOF
  859. fi
  860. if test -f 'externs.h'
  861. then
  862.     echo shar: "will not over-write existing file 'externs.h'"
  863. else
  864. cat << \SHAR_EOF > 'externs.h'
  865. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  866.  
  867. #ifndef IBMPC
  868. /* These variables need to be set */
  869.   /* Delete lines defining PRINT_FILE and HELP_FILE if non-existent or */
  870.   /* on machines which don't have exec() and fork() and the like */
  871. #define PRINT_FILE "/usr/ucb/more"
  872. #define HELP_FILE "/home/harmony/users/theory/wolfe/research/games/HELP"
  873. #endif
  874.  
  875. #include <string.h>
  876. #include <stdlib.h>
  877.  
  878.  
  879. #ifdef Ibm
  880. #define MAX_SIZE 3000
  881. #define INT_SIZE 16
  882. #else
  883. #define MAX_SIZE 32000
  884. #define INT_SIZE 32
  885. #endif
  886.  
  887. #define FALSE 0
  888. #define TRUE 1
  889.  
  890. #define MAXBUFF 200
  891.  
  892. /* print options */
  893. #define INTEGERS_FLAG (1<<0)
  894. #define NUMBERS_FLAG (1<<1)
  895. #define STARS_FLAG (1<<2)
  896. #define UPS_FLAG (1<<3)
  897. #define TINYS_FLAG (1<<4)
  898. #define ONS_FLAG (1<<12)
  899. #define VARS_FLAG (1<<5)
  900. #define EXPAND_FLAG (1<<6)
  901. #define ALL_FLAG (INTEGERS_FLAG|NUMBERS_FLAG|STARS_FLAG|UPS_FLAG|TINYS_FLAG|ONS_FLAG|\
  902.                   VARS_FLAG|EXPAND_FLAG|PROMPT_FLAG|NORMALIZE_FLAG)
  903. #define PROMPT_FLAG (1<<7)
  904. /* check if g = h.1* */
  905. #define EVALUATE_FLAG (1<<8)
  906. #define NORMALIZE_FLAG (1<<14)
  907. #define ECHO_INPUT_FLAG (1<<9)
  908. /* make unproven assumptions (corridors.c) for efficiency */
  909. #define ASSUME_FLAG (1<<10)
  910. /* make false assumptions (corridors.c) for efficiency -- in particular that the size of
  911.    an invading group is irrelevent */
  912. #define ASSUME2_FLAG (1<<15)
  913. /* reinitialize hash table between commands */
  914. #define CLEAN_FLAG (1<<11)
  915. /* output formulas in TeX */
  916. #define TEX_FLAG (1<<13)
  917.  
  918. /* hash table entries */
  919. #define UNEXPENDABLE_KEYS    (1 << 15)
  920. #define EXPENDABLE_KEYS        (1 << 14)
  921. #define OTHER_KEYS        (1 << 13)
  922. #define SIMPLIFY_KEY        ( 1 | UNEXPENDABLE_KEYS)
  923. #define PLUS_KEY        ( 2 | EXPENDABLE_KEYS)
  924. #define NEGATIVE_KEY        ( 3 | EXPENDABLE_KEYS)
  925. #define GE_KEY            ( 4 | EXPENDABLE_KEYS)
  926. #define NUM_UP_STAR_BABYKO_KEY    ( 5 | EXPENDABLE_KEYS)
  927. #define COOL_KEY        ( 8 | EXPENDABLE_KEYS)
  928. #define TEMPERATURE_KEY        ( 9 | EXPENDABLE_KEYS)
  929. #define FREEZE_KEY        (10 | EXPENDABLE_KEYS)
  930. #define HEAT_KEY        (12 | EXPENDABLE_KEYS)
  931. #define MULT_KEY        (13 | EXPENDABLE_KEYS)
  932. #define AW_KEY            (14 | EXPENDABLE_KEYS)
  933. #define VAR_KEY            (15 | UNEXPENDABLE_KEYS)
  934. #define CORRIDOR_KEY        (16 | OTHER_KEYS)
  935. #define CORRIDOR_VALUE_KEY    (18 | EXPENDABLE_KEYS)
  936. #define INT_KO_STAR_KEY        (19 | UNEXPENDABLE_KEYS)
  937. #define INT_BABYKO_KEY        (20 | UNEXPENDABLE_KEYS)
  938. #define DOMINO_KEY        (21 | EXPENDABLE_KEYS)
  939. /* These indicate what to do when hash table needs space.
  940.    OTHER_KEYS are sometimes expendable, depending on context */
  941.  
  942. /* ARGUMENT_SYMBOL is the internal string representation of the argument to 
  943.    cool_function and warm_function. */
  944. #define ARGUMENT_SYMBOL "\1"
  945.  
  946. typedef int boolean;
  947. typedef unsigned game_type;
  948. typedef game_type (* function_type)();
  949. typedef boolean (* test_type) (game_type, game_type);
  950.  
  951. extern void        stat ();
  952. extern void        myerror (char *);
  953. extern int        game_parse(char *);
  954. extern char **        envp;
  955. extern unsigned long    flags;
  956.  
  957. extern void _exit(int), perror(const char *), execle();
  958. extern int printf(const char *, ...), vfork(), wait(), yyparse(), fflush();
  959. extern char *gets();
  960. #ifdef __TURBOC__
  961. extern void exit(int), free(void *);
  962. extern long coreleft(void);
  963. #endif
  964. SHAR_EOF
  965. fi
  966. if test -f 'games.c'
  967. then
  968.     echo shar: "will not over-write existing file 'games.c'"
  969. else
  970. cat << \SHAR_EOF > 'games.c'
  971. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  972.  
  973. #include <stdio.h>
  974. #include "externs.h"
  975. #include "rational.h"
  976. #include "list.h"
  977. #include "hash.h"
  978. #include "operations.h"
  979. #include "output.h"
  980.  
  981. unsigned long        flags = ALL_FLAG;
  982. char **envp;
  983.  
  984. void myerror(char *s) {
  985.     perror (s);
  986. }
  987.  
  988. void help() {
  989. #ifdef PRINT_FILE
  990. #ifdef HELP_FILE
  991.     switch (vfork ()) {
  992.     case -1:
  993.         perror ("Sorry, couldn't fork");
  994.         break;
  995.     case 0:
  996.         execle (PRINT_FILE, PRINT_FILE, HELP_FILE, 0, envp);
  997.         perror ("Sorry, couldn't exec");
  998.         _exit (-1);
  999.     default:
  1000.         if (wait(0) < 0)
  1001.             perror ("wait in help");
  1002.     }
  1003. #endif
  1004. #endif
  1005. }
  1006.  
  1007. extern char *yysptr;
  1008. extern char yysbuf[];
  1009. int game_parse (char *s) {
  1010.     parser_input = s;
  1011.     parser_output = NO_GAME;
  1012.     if (flags & CLEAN_FLAG) clean();
  1013.     yysptr = yysbuf;    /* Initialize lex's unput buffer to empty in case 
  1014.                  * last call to yyparse() bombed. */
  1015.     if (yyparse()) return NO_GAME;
  1016.     else return parser_output;
  1017. }
  1018.  
  1019. extern int game_stat();
  1020. extern int hash_stat();
  1021. extern int list_stat();
  1022. extern int corridor_stat();
  1023.  
  1024. void stat (void) {
  1025. #ifdef __TURBOC__
  1026.     printf ("total lists: %u; coreleft %u\n",
  1027.         hash_stat() + game_stat() + corridor_stat() + list_stat(), coreleft());
  1028. #else
  1029.     printf ("total lists: %u\n",
  1030.         hash_stat() + game_stat() + corridor_stat() + list_stat());
  1031. #endif
  1032. }
  1033.  
  1034. void games (void) {
  1035.     char input[MAXBUFF];
  1036.     game_type g;
  1037.  
  1038.     printf ("Type help, if you need it, control-D to exit\n");
  1039.     for (;;) {
  1040.         if (flags & PROMPT_FLAG) printf ("> ");
  1041.         if (gets (input) == NULL) {
  1042.             printf ("\n");
  1043.             exit(0);    /* eof */
  1044.         }
  1045.         if (flags & ECHO_INPUT_FLAG) printf ("%60s => ", input);
  1046.         fflush (stdout);
  1047.         strcat (input, "\n");
  1048.         g = game_parse (input);
  1049.         if (g) set_var (dummy_var = make_var ("$"), g);
  1050.         if (g) game_printf (g);
  1051.         fflush (stdout);
  1052.     }
  1053. }
  1054. SHAR_EOF
  1055. fi
  1056. if test -f 'grammar.y'
  1057. then
  1058.     echo shar: "will not over-write existing file 'grammar.y'"
  1059. else
  1060. cat << \SHAR_EOF > 'grammar.y'
  1061. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  1062. /* Includes mostly code written by David Moews */
  1063.  
  1064. %{
  1065. #include "externs.h"
  1066. #include "rational.h"
  1067. #include "list.h"
  1068. #include "operations.h"
  1069. #include "output.h"
  1070. #include "corridors.h"
  1071. #include "bitmatrix.h"
  1072. #include "domino.h"
  1073.     
  1074.  
  1075. #define vsl(a,b) make(list_copy_1((a)), (b))
  1076. #define vsr(a,b) make((a), list_copy_1((b)))
  1077.  
  1078. boolean non_syn_error = FALSE;
  1079. %}
  1080.  
  1081. %start line
  1082.  
  1083. %union {
  1084.     int ival;
  1085.     Q_type qval;
  1086.     list_type lval;
  1087.     game_type gval;
  1088.         var_type vval;
  1089. }
  1090.  
  1091. %type <vval> vs
  1092. %type <ival> mask c ce
  1093. %type <lval> l cl nl
  1094. %type <gval> num atom atoms numatoms term
  1095. %type <gval> g gt gts line gop gterm
  1096. %type <gval> gp        /* plain g (w/o bars in outer level) */
  1097. %type <gval> gb gb1 gb2 gb3 gb4
  1098.  
  1099. %token <ival> NUM ZEROS BARZEROS ONNUM
  1100. %token <vval> S
  1101. %token ENDOFSTRING
  1102. %token FREEZE CHILL MEAN TEMPERATURE AW ON OFF
  1103. %token HELP RESET STAT
  1104. %token INTEGERS NUMBERS STARS UPS TINYS ONS VARS EXPAND ALL EVALUATE NORMALIZE PROMPT ECHO_ ASSUME ASSUME2 CLEAN TEX
  1105. %token BAR BARR BARRR BARRRR BARRRRR NO
  1106. %token MINUS_K MINUS_k
  1107. %token TINY MINY
  1108. %token UNKNOWN
  1109. %token CORRIDOR DOMINO SALTUS PERIOD
  1110.  
  1111. %%
  1112. line    : ENDOFSTRING /*empty*/    { }
  1113.     | error ENDOFSTRING    {if (!non_syn_error)
  1114.                         myerror("Syntax error.");
  1115.                                  non_syn_error = FALSE;
  1116.                  yyerrok;
  1117.                    }
  1118.     | g ENDOFSTRING        {parser_output = $1; YYACCEPT;}
  1119.     | g '?' g ENDOFSTRING    {(void)printf("%s\n", compare($1, $3));
  1120.                     parser_output = NO_GAME;}
  1121.     | mask ENDOFSTRING    {flags |= $1;}
  1122.     | NO mask ENDOFSTRING     {flags &= ~$2;}
  1123.     | HELP ENDOFSTRING    {(void) help();}
  1124.     | STAT ENDOFSTRING    {stat();}
  1125.     | RESET ENDOFSTRING    {reinit();}
  1126.     | DOMINO nl ENDOFSTRING    {parser_output = domino ($2);}
  1127.     | SALTUS ENDOFSTRING    {parser_output = saltus; YYACCEPT;}
  1128.     | SALTUS g ENDOFSTRING    {saltus = $2;}
  1129.     | PERIOD ENDOFSTRING    {parser_output = g_int (period); YYACCEPT;}
  1130.     | PERIOD NUM ENDOFSTRING{period = $2;}
  1131.     ;    
  1132.  
  1133. mask    : INTEGERS        {$$ = INTEGERS_FLAG;}
  1134.     | NUMBERS        {$$ = NUMBERS_FLAG;}
  1135.     | STARS            {$$ = STARS_FLAG;}
  1136.     | UPS            {$$ = UPS_FLAG;}
  1137.     | TINYS            {$$ = TINYS_FLAG;}
  1138.     | ONS            {$$ = ONS_FLAG;}
  1139.     | EXPAND        {$$ = EXPAND_FLAG;}
  1140.     | VARS            {$$ = VARS_FLAG;}
  1141.     | ALL            {$$ = ALL_FLAG;}
  1142.     | PROMPT        {$$ = PROMPT_FLAG;}
  1143.     | EVALUATE        {$$ = EVALUATE_FLAG;}
  1144.     | NORMALIZE        {$$ = NORMALIZE_FLAG;}
  1145.     | ECHO_            {$$ = ECHO_INPUT_FLAG;}
  1146.     | ASSUME        {$$ = ASSUME_FLAG;}
  1147.     | ASSUME2        {$$ = ASSUME2_FLAG;}
  1148.     | CLEAN            {$$ = CLEAN_FLAG;}
  1149.     | TEX            {$$ = TEX_FLAG;}
  1150.     ;
  1151.  
  1152. nl    :             {$$ = list_make();}
  1153.     | NUM nl        {list_insert_unsorted ($2, $1), $$ = $2;}
  1154.      
  1155.  
  1156. c    : '(' cl ')'                {$$ = corridor_get ($2);
  1157.                         list_free ($2);}
  1158.     ;
  1159.  
  1160. cl    : ce                    {$$ = list_copy_1 ($1);}
  1161.     | cl ce                    {list_insert ($1, $2); $$ = $1;}
  1162.     ;
  1163.  
  1164. ce    : NUM                    {$$ = SIZE | $1;}
  1165.     | 'b' NUM                {$$ = BLOCKED | $2;}
  1166.     | 'u' NUM                {$$ = UNBLOCKED | $2;}
  1167.     | c                    {$$ = FOLLOWER | $1;}
  1168.     ;
  1169.  
  1170. l     : gt                    {$$ = list_copy_1($1);}
  1171.     | l ',' gt                {list_insert ($$ = $1, $3);}
  1172.     ;
  1173.  
  1174. gb1    : l BAR l                {$$ = make($1, $3);}
  1175.     | l BAR gb1                {$$ = vsr($1, $3);}
  1176.     | ZEROS BAR gt                {$$ = zeros_vs ($3, $1);}
  1177.     | gt BARZEROS                {$$ = vs_zeros ($1, $2);}
  1178.     ;
  1179.  
  1180. gb2    : gb1                    {$$ = $1;}
  1181.     | l BARR l                {$$ = make($1, $3);}
  1182.     | l BARR gb2                {$$ = vsr($1, $3);}
  1183.     | gb1 BARR l                {$$ = vsl($1, $3);}
  1184.     | gb1 BARR gb2                {$$ = vs ($1, $3);}
  1185.     ;
  1186.  
  1187. gb3    : gb2                    {$$ = $1;}
  1188.     | l BARRR l                {$$ = make ($1, $3);}
  1189.     | l BARRR gb3                {$$ = vsr($1, $3);}
  1190.     | gb2 BARRR l                {$$ = vsl($1, $3);}
  1191.     | gb2 BARRR gb3                {$$ = vs ($1, $3);}
  1192.     ;
  1193.  
  1194. gb4    : gb3                    {$$ = $1;}
  1195.     | l BARRRR l                {$$ = make ($1, $3);}
  1196.     | l BARRRR gb4                {$$ = vsr($1, $3);}
  1197.     | gb3 BARRRR l                {$$ = vsl($1, $3);}
  1198.     | gb3 BARRRR gb4            {$$ = vs ($1, $3);}
  1199.     ;
  1200.  
  1201. gb     : gb4                    {$$ = $1;}
  1202.     | l BARRRRR l                {$$ = make ($1, $3);}
  1203.     | l BARRRRR gb                {$$ = vsr($1, $3);}
  1204.     | gb4 BARRRRR l                {$$ = vsl($1, $3);}
  1205.     | gb4 BARRRRR gb            {$$ = vs ($1, $3);}
  1206.     ;
  1207.  
  1208. g    : vs '=' g                {set_var($1, $$ = $3);}
  1209.     | gts;
  1210.     ;
  1211.  
  1212. gts    : gterm                    {$$ = $1;}
  1213.     | gts '+' gterm                {$$ = plus($1, $3);}
  1214.     | gts '-' gterm                {$$ = minus($1, $3);}
  1215.     ;
  1216.  
  1217. gterm    : gt                    {$$ = $1;}
  1218.     | gb                    {$$ = $1;}
  1219.     ;
  1220.  
  1221. gt    : gop                    {$$ = $1;}
  1222.     | gp                    {$$ = $1;}
  1223.     | gp '[' g ']'                {$$ = cool ($1, mean ($3));}
  1224.     | gp '<' g '>'                {$$ = gexp ($1, Q_p (mean ($3)));}
  1225.     | gp '.' gp                {$$ = mult($1, $3);}
  1226.     | gp ONNUM                {$$ = on ($1, $2);}
  1227.     | gt gop                {$$ = plus ($1,$2);}
  1228.     ;
  1229.  
  1230. gop    : FREEZE gp                {$$ = freeze ($2);}
  1231.     | '%' gp                {$$ = overheat ($2, NO_GAME, NO_GAME);}
  1232.     | '%' '<' g '>' gp            {$$ = heat ($5, $3);}
  1233.     | '%' '[' g ']' '<' g '>' gp        {$$ = overheat ($8, $3, $6);}
  1234.     | ON '[' g ']' '<' g '>'        {$$ = on ($3, Q_p (mean ($6)));}
  1235.     | OFF '[' g ']' '<' g '>'        {$$ = off ($3, Q_p (mean ($6)));}
  1236.     | CORRIDOR c                {$$ = corridor_val ($2);}
  1237.     | MEAN gp                {$$ = num (mean ($2));}
  1238.     | TEMPERATURE gp            {$$ = num (temperature ($2));}
  1239.     | AW gp                    {$$ = atomic_weight ($2);}
  1240.     ;
  1241.  
  1242. num    : NUM                    {$$ = num(Q_int($1));}
  1243.     | NUM '/' NUM                {Q_error = FALSE; 
  1244.                                                  $$ = num(Q($1, $3)); 
  1245.                                                  if (Q_error) 
  1246.                                                  {  
  1247.                                                    non_syn_error = TRUE; 
  1248.                                                    YYERROR;
  1249.                                                  } 
  1250.                                                 }
  1251.     | '-' vs                {$$ = negative (get_var ($2));}
  1252.     | '-' NUM                {$$ = num(Q_int(-$2));}
  1253.     | '-' NUM '/' NUM            {Q_error = FALSE; 
  1254.                               $$ = num(Q(-$2, $4)); 
  1255.                                                  if (Q_error)  
  1256.                                                  { 
  1257.                                                   non_syn_error = TRUE; 
  1258.                                                   YYERROR;
  1259.                                                  } 
  1260.                                                 }
  1261.     ;
  1262.  
  1263. atom    : '*'                    {$$ = star(1);}
  1264.     | '*' NUM                {$$ = star($2);}
  1265.     | '^'                    {$$ = up(1);}
  1266.     | '^' NUM                {$$ = up($2);}
  1267.     | 'v'                    {$$ = down(1);}
  1268.     | 'v' NUM                {$$ = down($2);}
  1269.     | TINY '[' g ']'            {$$ = tiny ($3);}
  1270.     | MINY '[' g ']'            {$$ = miny ($3);}
  1271.     | 'K'                    {$$ = ko;}
  1272.     | MINUS_K                {$$ = kobar;}
  1273.     | 'k'                    {$$ = babyko;}
  1274.     | MINUS_k                {$$ = babykobar;}
  1275.     | '{' g '}'                {$$ = $2;}
  1276.     | '(' g ')'                {$$ = $2;}
  1277.     ;
  1278.  
  1279. atoms    : atom                    {$$ = $1;}
  1280.     | atoms atom                {$$ = plus ($1, $2);}
  1281.     ;
  1282.  
  1283. numatoms: atoms                    {$$ = $1;}
  1284.     | num                    {$$ = $1;}
  1285.     | num atoms                {$$ = plus($1, $2);}
  1286.     ;
  1287.  
  1288. term    : numatoms                {$$ = $1;}
  1289. /*    | numatoms '%' numatoms            {$$ = plus ($1, mult ($3, one_star));}*/
  1290.     ;
  1291.  
  1292. gp    : term                    {$$ = $1;}
  1293.     | vs                    {$$ = get_var($1);
  1294.                          list_free ($1);
  1295.                          if ($$ == NO_GAME) {
  1296.                                                    myerror("Variable not set.");
  1297.                                                    non_syn_error = TRUE;
  1298.                                                    YYERROR;
  1299.                                                  }
  1300.                         }
  1301.     | '{' l BAR '}'                {$$ = make($2, list_make());}
  1302.     | '{' BAR l '}'                {$$ = make(list_make(), $3);}
  1303.     | '{' BAR '}'                {$$ = zero;}
  1304.     | '{' l BARR '}'            {$$ = make($2, list_make());}
  1305.     | '{' gb1 BARR '}'            {$$ = vsl($2, list_make());}
  1306.     | '{' BARR l '}'            {$$ = make(list_make(), $3);}
  1307.     | '{' BARR gb1 '}'            {$$ = vsr(list_make(), $3);}
  1308.     | '{' BARR '}'                {$$ = zero;}
  1309.     | '{' l BARRR '}'            {$$ = make($2, list_make());}
  1310.     | '{' gb2 BARRR '}'            {$$ = vsl($2, list_make());}
  1311.     | '{' BARRR l '}'            {$$ = make(list_make(), $3);}
  1312.     | '{' BARRR gb2 '}'            {$$ = vsr(list_make(), $3);}
  1313.     | '{' BARRR '}'                {$$ = zero;}
  1314.     | '{' l BARRRR '}'            {$$ = make($2, list_make());}
  1315.     | '{' gb3 BARRRR '}'            {$$ = vsl($2, list_make());}
  1316.     | '{' BARRRR l '}'            {$$ = make(list_make(), $3);}
  1317.     | '{' BARRRR gb3 '}'            {$$ = vsr(list_make(), $3);}
  1318.     | '{' BARRRR '}'            {$$ = zero;}
  1319.     | '{' l BARRRRR '}'            {$$ = make($2, list_make());}
  1320.     | '{' gb4 BARRRRR '}'            {$$ = vsl($2, list_make());}
  1321.     | '{' BARRRRR l '}'            {$$ = make(list_make(), $3);}
  1322.     | '{' BARRRRR gb4 '}'            {$$ = vsr(list_make(), $3);}
  1323.     | '{' BARRRRR '}'            {$$ = zero;}
  1324.     ;
  1325.  
  1326. vs    : S                    {$$ = $1;}
  1327.     ;
  1328. %%
  1329. char *parser_input;
  1330. game_type parser_output;
  1331.  
  1332. void yyerror (s)
  1333.     char *s;
  1334. {
  1335. }
  1336.  
  1337. #include "parse.c"
  1338. SHAR_EOF
  1339. fi
  1340. if test -f 'hash.c'
  1341. then
  1342.     echo shar: "will not over-write existing file 'hash.c'"
  1343. else
  1344. cat << \SHAR_EOF > 'hash.c'
  1345. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  1346.  
  1347. #include "externs.h"
  1348. #include "list.h"
  1349. #include "hash.h"
  1350.  
  1351. #define HNIL ((hash_chain_type) 0)
  1352. #define Chain hash_last_chain
  1353.  
  1354. long unsigned        hash_count=0;
  1355. long unsigned        hash_cleanings=0;
  1356. hash_chain_type        hash_last_chain;
  1357. static hash_chain_type    hash_free_list = HNIL;
  1358. hash_chain_type        hash_table[TABLE_SIZE];
  1359.  
  1360. static hash_chain_type hash_get_cell (void) {
  1361.     hash_chain_type cell, p;
  1362.     int i;
  1363.  
  1364.     if (hash_free_list == HNIL) {
  1365.         if (!(hash_free_list = (hash_chain_type)
  1366.               malloc(HASH_CELL_BLOCK_SIZE * sizeof (struct hash_chain_struct))))
  1367.             myerror("hash_get_cell: malloc couldn't free block");
  1368.         for (i = 1, p=hash_free_list; i < HASH_CELL_BLOCK_SIZE;i++, p++)
  1369.             p->next = p + 1;
  1370.         p++;
  1371.         p->next = HNIL;
  1372.     }
  1373.     cell = hash_free_list;
  1374.     hash_free_list = hash_free_list -> next;
  1375.     hash_count++;
  1376.     return cell;
  1377. }
  1378.  
  1379. static void hash_free_cell (hash_chain_type list) {
  1380.     list -> next = hash_free_list;
  1381.     hash_free_list = list;
  1382.     hash_count--;
  1383. }
  1384.  
  1385. void hash_init (void) {
  1386.     int i;
  1387.  
  1388.     for (i=0;i<TABLE_SIZE;i++) hash_table[i] = HNIL;
  1389. }
  1390.  
  1391. void hash_clear(int keys, int rate) {
  1392.     int i;
  1393.     static int random=0;
  1394.     hash_chain_type chain, next;
  1395.     
  1396.     for (i = 0; i < TABLE_SIZE; i++) {
  1397.         while ((chain = hash_table[i]) != HNIL
  1398.                && (chain->id & keys)
  1399.                && (random = (random+37) % 100) < rate) {
  1400.             hash_table[i] = chain->next;
  1401.             list_free (chain->key);
  1402.             hash_free_cell (chain);
  1403.         }
  1404.         if (chain != HNIL) {
  1405.             while ((next = chain->next) != HNIL)
  1406.                 if (   (next->id & keys)
  1407.                     && (random = (random+37) % 100) < rate) {
  1408.                     chain->next = next->next;
  1409.                     list_free (next->key);
  1410.                     hash_free_cell (next);
  1411.                 }
  1412.                 else chain = next;
  1413.         }
  1414.     }
  1415. }
  1416.  
  1417. int hash_function (hash_id_type id, hash_key_type key) {
  1418.     unsigned long val;
  1419.  
  1420.     val = (A * (id%M) + B) % M;
  1421.     for (key = list_start (key); key != NIL; key = list_rest (key))
  1422.         val = (A * (val + list_pick(key) + 1) + B) % M;
  1423.     if (val < 0) val += M;
  1424.     return val % TABLE_SIZE;
  1425. }
  1426.  
  1427. boolean hash_test (hash_id_type id, hash_key_type key) {
  1428.     for (Chain = hash_table[hash_function(id,key)]; Chain != HNIL; Chain = Chain->next)
  1429.         if ((Chain->id == id) && list_equal(Chain->key, key))
  1430.             return TRUE;
  1431.     return FALSE;
  1432. }
  1433.         
  1434. #define current_space() ((long) (hash_count * sizeof (struct hash_chain_struct) + list_count * sizeof (struct list_struct)))
  1435. void hash_put (hash_id_type id, hash_key_type key, hash_value_type value) {
  1436.     hash_chain_type new;
  1437.     int i;
  1438.     static long last_cleaned=0, last_warned=0;
  1439.         
  1440.     if (current_space() > SPACE_CLEAN)
  1441.         if (current_space() - last_cleaned > SPACE_INTERVAL) {
  1442.             hash_clear (EXPENDABLE_KEYS, 50);
  1443.             last_cleaned = current_space();
  1444.             hash_cleanings++;
  1445.         } else if (current_space() > SPACE_WARNING
  1446.                && (current_space() - last_warned > SPACE_INTERVAL)) {
  1447.             perror ("WARNING -- running out of space.");
  1448.             last_warned = current_space();
  1449.         }
  1450.     new = hash_get_cell();
  1451.     new -> value = value;
  1452.     new -> id = id;
  1453.     new -> key = key;
  1454.  
  1455.     i = hash_function(id, key);
  1456.     new -> next = hash_table[i];
  1457.     hash_table[i] = new;
  1458.     return;
  1459. }
  1460.  
  1461. hash_value_type hash_get (hash_id_type id, hash_key_type key) {
  1462.     for (Chain = hash_table[hash_function(id,key)]; Chain != HNIL; Chain = Chain->next)
  1463.         if ((Chain->id == id) && list_equal(Chain->key, key))
  1464.             return Chain->value;
  1465.     myerror ("hash_get: not in table");
  1466.     return 0;
  1467. }
  1468.  
  1469. void hash_delete (hash_id_type id, hash_key_type key) {
  1470.     hash_chain_type chain, next;
  1471.  
  1472.     chain = hash_table[hash_function(id,key)];
  1473.     if (chain == HNIL) return;
  1474.     else if ((chain->id == id) && list_equal(chain->key, key)) {
  1475.         hash_table[hash_function(id,key)] = chain -> next;
  1476.         list_free (chain->key);
  1477.         hash_free_cell (chain);
  1478.     } else while ((next = (chain->next)) != HNIL)
  1479.         if ((next->id == id) && list_equal(next->key, key)) {
  1480.             chain->next = next->next;
  1481.             list_free (next->key);
  1482.             hash_free_cell (next);
  1483.             return;
  1484.         } else chain = next;
  1485.     return;
  1486. }
  1487.  
  1488. unsigned long hash_stat (void) {
  1489.     unsigned long n=0, c[30], j, k[30], i;
  1490.     hash_chain_type chain;
  1491.  
  1492.     for (i = 0; i < 30; i++) c[i]=k[i]=0;
  1493.     for (i = 0; i < TABLE_SIZE; i++) {
  1494.         for (j=0, chain = hash_table[i]; chain != HNIL;j++, chain = chain->next) {
  1495.             n = n + list_length (chain->key) + 1;
  1496.             (k[chain->id & 31])++;
  1497.         }
  1498.         if (j < 30)
  1499.             c[j]++;
  1500.         else
  1501.             printf ("Table entry %u has %u elements\n", i, j);
  1502.     }
  1503.     printf ("Distribution of hash table chains by length:\n");
  1504.     for (i = 0; i < 30; i++) printf ("%u ", c[i]);
  1505.     printf ("\nDistribution of hash table usage by id:\n");
  1506.     for (i = 0; i < 30; i++) printf ("%u ", k[i]);
  1507.     printf ("\n");
  1508.     printf ("hash cleanings performed: %u; hash table lists: %u; ", hash_cleanings, n);
  1509.     return n;
  1510. }
  1511. SHAR_EOF
  1512. fi
  1513. if test -f 'hash.h'
  1514. then
  1515.     echo shar: "will not over-write existing file 'hash.h'"
  1516. else
  1517. cat << \SHAR_EOF > 'hash.h'
  1518. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  1519.  
  1520. /* Hash table implemented using chaining.
  1521.  * NOTE:  There is only one hash table!  The first argument is an integer,
  1522.  * which will generally be a unique identifier to which hash you want,
  1523.  * simulating multiple hash tables (ie. the real key is constructed from
  1524.  * the pair    (id, key).  The intended purpose is for memoizing
  1525.  * functions, in which case the first argument should uniquely identify the
  1526.  * function.  All functions are written in a type indepenedent manner except
  1527.  * hash_fuction().
  1528.  */
  1529.  
  1530. #define HASH_CELL_BLOCK_SIZE 1000    /* size of mallocs, when needed */
  1531. #define TABLE_SIZE MAX_SIZE
  1532. #define A ((unsigned long) 67343)
  1533. #define B ((unsigned long) 72763)
  1534. #define M ((unsigned long) 99991)
  1535.  
  1536. #ifdef IBMPC
  1537. #define SPACE_CLEAN    ((long) 200000)
  1538. #define SPACE_INTERVAL    ((long) 10000)
  1539. #define SPACE_WARNING    ((long) 500000)
  1540. #else
  1541. #define SPACE_CLEAN    ((long) 5000000)
  1542. #define SPACE_INTERVAL    ((long) 1000000)
  1543. #define SPACE_WARNING    ((long) 8000000)
  1544. #endif
  1545.  
  1546. typedef game_type hash_value_type;
  1547. typedef int hash_id_type;
  1548. typedef list_type hash_key_type;
  1549.  
  1550. typedef struct hash_chain_struct {
  1551.     hash_value_type value;
  1552.     hash_id_type id;
  1553.     hash_key_type key;
  1554.     struct hash_chain_struct *next;
  1555. } *hash_chain_type;
  1556.  
  1557. extern hash_chain_type    hash_table[TABLE_SIZE];
  1558. extern hash_chain_type    hash_last_chain;
  1559.  
  1560. extern void        hash_init (void);
  1561. extern void        hash_clear (int, int);
  1562. extern boolean        hash_test (hash_id_type, hash_key_type);
  1563. extern void        hash_put (hash_id_type, hash_key_type, hash_value_type);
  1564. extern hash_value_type    hash_get (hash_id_type, hash_key_type);
  1565. extern void        hash_delete (hash_id_type, hash_key_type);
  1566.  
  1567. #define hash_get_last() (hash_last_chain->value)
  1568. SHAR_EOF
  1569. fi
  1570. if test -f 'list.c'
  1571. then
  1572.     echo shar: "will not over-write existing file 'list.c'"
  1573. else
  1574. cat << \SHAR_EOF > 'list.c'
  1575. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  1576.  
  1577. #include "externs.h"
  1578. #include "list.h"
  1579.  
  1580. long unsigned list_count=0;
  1581. static list_type list_free_list = NIL;
  1582.        list_type list_0 = NIL;
  1583. static list_type ll1 = NIL;        /* A list of length 1 */
  1584. static list_type ll2 = NIL;        /*                  2 */
  1585. static list_type ll3 = NIL;        /*                  3 */
  1586.  
  1587. static list_type list_get_cell (void) {
  1588.     list_type cell, p;
  1589.     int i;
  1590.  
  1591.     if (list_free_list == NIL) {
  1592.         if (!(list_free_list = (list_type)
  1593.               malloc(LIST_CELL_BLOCK_SIZE * sizeof (struct list_struct))))
  1594.             myerror("list_get_cell: malloc couldn't free block");
  1595.         for (i = 1, p=list_free_list; i < LIST_CELL_BLOCK_SIZE;i++, p++)
  1596.             p->next = p+1;
  1597.         p->next = NIL;
  1598.     }
  1599.     cell = list_free_list;
  1600.     list_free_list = list_free_list->next;
  1601.     list_count++;
  1602.     return cell;
  1603. }
  1604.  
  1605. static void list_free_cell (list_type l) {
  1606.     l -> next = list_free_list;
  1607.     list_free_list = l;
  1608.     list_count--;
  1609.     return;
  1610. }
  1611.  
  1612. void list_init(void) {
  1613.     if (list_0 == NIL) {
  1614.         list_0 = list_make();
  1615.         ll1 = list_make();
  1616.         list_insert (ll1, 0);
  1617.         ll2 = list_make();
  1618.         list_insert (ll2, 0);
  1619.         list_insert (ll2, 0);
  1620.         ll3 = list_make();
  1621.         list_insert (ll3, 0);
  1622.         list_insert (ll3, 0);
  1623.         list_insert (ll3, 0);
  1624.     }
  1625.     return;
  1626. }
  1627.  
  1628. list_type list_1(list_elt_type e) {
  1629.     ll1->next->elt = e;
  1630.     return ll1;
  1631. }
  1632.  
  1633. list_type list_unordered_2(list_elt_type e1, list_elt_type e2) {
  1634.     if (list_elt_less (e1, e2)) {
  1635.         ll2->next->elt = e1;
  1636.         ll2->next->next->elt = e2;
  1637.     } else {
  1638.         ll2->next->elt = e2;
  1639.         ll2->next->next->elt = e1;
  1640.     }
  1641.     return ll2;
  1642. }
  1643.  
  1644. list_type list_2(list_elt_type e1, list_elt_type e2) {
  1645.     ll2->next->elt = e1;
  1646.     ll2->next->next->elt = e2;
  1647.     return ll2;
  1648. }
  1649.  
  1650. list_type list_3(list_elt_type e1, list_elt_type e2, list_elt_type e3) {
  1651.     ll3->next->elt = e1;
  1652.     ll3->next->next->elt = e2;
  1653.     ll3->next->next->next->elt = e3;
  1654.     return ll3;
  1655. }
  1656.  
  1657. list_type list_make(void) {
  1658.     list_type header;
  1659.  
  1660.     header = list_get_cell();
  1661.     header -> next = NIL;
  1662.     list_elt_small (header -> elt);
  1663.     return header;
  1664. }
  1665.  
  1666. void list_insert (list_type l, list_elt_type e) {
  1667.     list_type cell;
  1668.  
  1669.     while (l->next != NIL && (list_elt_less (l->next->elt, e)))
  1670.         l = l->next;
  1671.     cell = list_get_cell();
  1672.     cell->elt = e;
  1673.     cell->next = l->next;
  1674.     l->next = cell;
  1675.     return;
  1676. }
  1677.  
  1678. void list_insert_unsorted (list_type l, list_elt_type e) {
  1679.     list_type cell;
  1680.  
  1681.     cell = list_get_cell();
  1682.     cell->elt = e;
  1683.     cell->next = l->next;
  1684.     l->next = cell;
  1685.     return;
  1686. }
  1687.  
  1688. boolean list_member (list_type l, list_elt_type e) {
  1689.     while ((l = l -> next) != NIL)
  1690.         if (list_elt_equal (l->elt, e))
  1691.             return TRUE;
  1692.     return FALSE;
  1693. }
  1694.  
  1695. int list_search (list_type l, list_elt_type e) {
  1696.     int i = 0;
  1697.  
  1698.     while ((l = l->next) != NIL) {
  1699.         i++;
  1700.         if (list_elt_equal (l->elt, e))
  1701.             return i;
  1702.     }
  1703.     return 0;
  1704. }
  1705.  
  1706. int list_length (list_type l) {
  1707.     int i = 0;
  1708.     
  1709.     while ((l = l->next) != NIL)
  1710.         i++;
  1711.     return i;
  1712. }
  1713.  
  1714. void list_delete (list_type l, list_elt_type e) {
  1715.     list_type temp;
  1716.  
  1717.     while (l->next != NIL && ! list_elt_equal (e, l->next->elt))
  1718.         l = l->next;
  1719.     if (!list_elt_equal (e, l->next->elt)) {
  1720.         myerror ("list_delete: element not in list");
  1721.         return;
  1722.     }
  1723.     temp = l->next->next;
  1724.     list_free_cell (l->next);
  1725.     l->next = temp;
  1726.     return;
  1727. }
  1728.  
  1729. void list_delete_nth (list_type l, int n) {
  1730.     list_type temp;
  1731.  
  1732.     while (l->next != NIL && --n > 0)
  1733.         l = l->next;
  1734.     if (l->next == NIL) return;
  1735.     temp = l->next->next;
  1736.     list_free_cell (l->next);
  1737.     l->next = temp;
  1738.     return;
  1739. }
  1740.  
  1741. void list_change_nth_to (list_type l, int n, list_elt_type e) {
  1742.     while (l->next != NIL && n-- > 0)
  1743.         l = l->next;
  1744.     l->elt = e;
  1745.     return;
  1746. }
  1747.  
  1748. list_elt_type list_first (list_type l) {
  1749.     return l->next->elt;
  1750. }
  1751.  
  1752. list_elt_type list_nth (list_type l, int n) {
  1753.     while ((l->next) != NIL && n-- > 0)
  1754.         l = l->next;
  1755.     return l -> elt;
  1756. }
  1757.  
  1758. void list_free (list_type l) {
  1759.     list_type rest;
  1760.  
  1761.     if (l == NIL) return;
  1762.     while ((rest = (l -> next)) != NIL) {
  1763.         list_free_cell (l);
  1764.         l = rest;
  1765.     }
  1766.     list_free_cell (l);
  1767.     return;
  1768. }
  1769.  
  1770. boolean list_equal (list_type l1, list_type l2) {
  1771.     for (;;) {
  1772.         l1 = l1->next;
  1773.         l2 = l2->next;
  1774.         if (l1 == NIL && l2 == NIL) return TRUE;
  1775.         else if (l1 == NIL || l2 == NIL
  1776.              || ! list_elt_equal (l1->elt,l2->elt)) return FALSE;
  1777.     }
  1778. }
  1779.  
  1780. list_type list_copy (list_type l1) {
  1781.     list_type l2, cell, l;
  1782.  
  1783.     l = l2 = list_make ();
  1784.     while ((l1 = l1 -> next) != NIL) {
  1785.         cell = list_get_cell ();
  1786.         cell->elt = l1->elt;
  1787.         l2->next = cell;
  1788.         l2 = cell;
  1789.     }
  1790.     l2->next = NIL;
  1791.     return l;
  1792. }
  1793.  
  1794. void list_clobber (list_type l1, list_type l2) {
  1795.     if (l1->next) list_free (l1->next);
  1796.     l1->next = l2->next;
  1797.     list_free_cell (l2);
  1798.     return;
  1799. }
  1800.  
  1801. list_type list_map (function_one_type f, list_type l1) {
  1802.     list_type l2;
  1803.  
  1804.     l2 = list_make ();
  1805.     while ((l1 = (l1->next)) != NIL)
  1806.         list_insert (l2, (*f)(l1->elt));
  1807.     return l2;
  1808. }
  1809.  
  1810. list_type list_mapll (function_two_type f, list_type l1, list_type l2) {
  1811.     list_type l3;
  1812.  
  1813.     l3 = list_make();
  1814.     while ((l1 = (l1->next)) != NIL && (l2 = (l2->next)) != NIL)
  1815.         list_insert (l3, (*f)(l1->elt, l2->elt));
  1816.     return l3;
  1817. }
  1818.  
  1819. list_type list_mapcomb (function_two_type f, list_type l1, list_type l2) {
  1820.     list_type l, l3;
  1821.  
  1822.     l3 = list_make();
  1823.     while ((l1 = (l1->next)) != NIL) {
  1824.         l = l2;
  1825.         while ((l = (l->next)) != NIL) {
  1826.             list_insert (l3, (*f)(l1->elt, l->elt));
  1827.         }
  1828.     }
  1829.     return l3;
  1830. }
  1831.  
  1832. list_type list_maplc (function_two_type f, list_type l1, list_elt_type e) {
  1833.     list_type l2;
  1834.     l2 = list_make();
  1835.     while ((l1 = (l1->next)) != NIL)
  1836.         list_insert (l2, (*f)(l1->elt, e));
  1837.     return l2;
  1838. }
  1839.  
  1840. list_type list_mapcl (function_two_type f, list_elt_type e, list_type l1) {
  1841.     list_type l2;
  1842.     l2 = list_make();
  1843.     while ((l1 = (l1 -> next)) != NIL)
  1844.         list_insert (l2, (*f)(e, l1->elt));
  1845.     return l2;
  1846. }
  1847.  
  1848. /* This combines two lists that are assumed to have positive integer elements
  1849.  * into a single list, where the elements of the second list are distinguished
  1850.  * by negating them.  Only use is to map two lists into one so that a game
  1851.  * (with lists of left and right followers) can be hashed using the hash
  1852.  * function which operates on only a one list argument.  * Cluge *
  1853.  */
  1854. list_type list_combine (list_type l1, list_type l2) {
  1855.     list_type l3;
  1856.     l3 = list_copy (l1);
  1857.     while ((l2 = (l2 -> next)) != NIL)
  1858.         list_insert (l3, -(l2 -> elt));
  1859.     return l3;
  1860.  
  1861. }
  1862.  
  1863. list_type list_union (list_type l1, list_type l2) {
  1864.     list_type l3;
  1865.     l3 = list_copy (l1);
  1866.     while ((l2 = (l2 -> next)) != NIL)
  1867.         if (!list_member (l3, l2->elt)) list_insert (l3, l2->elt);
  1868.     return l3;
  1869. }
  1870.  
  1871. list_type list_multi_union (list_type l1, list_type l2) {
  1872.     l1 = list_copy (l1);
  1873.     while ((l2 = (l2 -> next)) != NIL)
  1874.         list_insert (l1, l2->elt);
  1875.     return l1;
  1876. }
  1877.  
  1878. int list_stat(void) {
  1879.     list_type l;
  1880.     unsigned long n=0, t;
  1881.  
  1882.     if (list_free_list != NIL) n = 1;
  1883.     for (l = list_free_list; l->next != NIL; l = l->next) n++;
  1884.     t = list_length (list_0) + list_length (ll1) + list_length (ll2) + list_length (ll3) + 4;
  1885.     printf ("free list: %u; fixed lists: %u\n", n, t);
  1886.     return n + t;
  1887. }
  1888. SHAR_EOF
  1889. fi
  1890. if test -f 'list.h'
  1891. then
  1892.     echo shar: "will not over-write existing file 'list.h'"
  1893. else
  1894. cat << \SHAR_EOF > 'list.h'
  1895. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  1896.  
  1897. /* Maintains a SORTED list of elements.  Done with abstract data types,
  1898.  * except functions list_elt_less (e1, e2) and list_elt_equal(e1,e2)
  1899.  * compare 2 elements, list_elt_copy(e1,e2) copies elt e2 into e1,
  1900.  * and list_elt_small makes an element smaller than all other elements.
  1901.  * Lastly, list_combine is very implementation dependent for a cluge.
  1902.  */
  1903.  
  1904. #define LIST_CELL_BLOCK_SIZE 1000    /* size of mallocs, when needed */
  1905. #define list_elt_equal(x,y) (x==y)
  1906. #define list_elt_less(x,y) (x<y)
  1907. #define list_elt_copy(x,y) (x=y)
  1908. #define list_elt_small(x) (x = 0)
  1909.  
  1910. typedef int list_elt_type;
  1911. typedef struct list_struct {
  1912.     list_elt_type elt;
  1913.     struct list_struct *next;
  1914. } *list_type;
  1915.  
  1916. #define NIL (list_type) 0
  1917.  
  1918. #if 0
  1919. /* There are the politically correct definitions, since the objects
  1920.  * involved are really list_elt_type and not game_type.  But the
  1921.  * only functions that call them pass functions of type
  1922.  *
  1923.  * game_type (*f)(game_type, game_type),
  1924.  *
  1925.  * and since unsigned and int (game_type and list_elt_type) are
  1926.  * guaranteed to be the same size, there is no harm done.
  1927.  *
  1928.  * One must always worry about ones-complement and sign-magnitude machines,
  1929.  * but since we don't do comparisons or arithmetic (just assignment),
  1930.  * we're okay.
  1931.  *
  1932.  */
  1933. typedef list_elt_type (*function_two_type)(list_elt_type, list_elt_type);
  1934. typedef list_elt_type (*function_one_type)(list_elt_type);
  1935. #else
  1936. /* The politically incorrect but expedient declarations. */
  1937. typedef game_type (*function_two_type)(game_type, game_type);
  1938. typedef game_type (*function_one_type)(game_type);
  1939. #endif
  1940.  
  1941. extern long unsigned    list_count;    /* Number of lists allocated, not on free stack */
  1942.  
  1943. extern void        list_init(void);
  1944. extern list_type    list_make(void);
  1945. /* list_1, list_2, list_3,  and list_unordered_2 are functions returning
  1946.  * a recycled list of the indicated length.  Note that the list gets trashed the
  1947.  * next time the functions are called.  Used for temporary, fast, access. */
  1948. extern list_type    list_0;
  1949. extern list_type    list_1 (list_elt_type);
  1950. extern list_type    list_2 (list_elt_type, list_elt_type);
  1951. extern list_type    list_unordered_2 (list_elt_type, list_elt_type);
  1952. extern list_type    list_3 (list_elt_type, list_elt_type, list_elt_type);
  1953. extern void        list_insert (list_type, list_elt_type);
  1954. extern void        list_insert_unsorted (list_type, list_elt_type);
  1955. extern boolean        list_member (list_type, list_elt_type);
  1956. extern int        list_search (list_type, list_elt_type);
  1957. extern int        list_length (list_type);
  1958. extern void        list_delete (list_type, list_elt_type);
  1959. extern void        list_delete_nth (list_type, int);
  1960. extern void        list_change_nth_to (list_type, int, int);
  1961. extern list_elt_type    list_first  (list_type);
  1962. extern list_elt_type    list_nth (list_type, int);
  1963. extern void        list_free (list_type);
  1964. extern boolean        list_equal (list_type, list_type);
  1965. extern list_type    list_copy (list_type);
  1966. extern void        list_clobber (list_type, list_type);
  1967.         /* l1 <- l2 contents, clobbering both l1 and l2 old contents */
  1968. extern list_type    list_combine (list_type, list_type);
  1969.  
  1970. extern list_type    list_map (function_one_type, list_type);
  1971.     /* mapll acts on corresponding pairs, mapcomb acts on all pairs */
  1972. extern list_type    list_mapll (function_two_type, list_type, list_type);
  1973. extern list_type    list_mapcomb (function_two_type, list_type, list_type);
  1974. extern list_type    list_maplc (function_two_type, list_type, list_elt_type);
  1975. extern list_type    list_mapcl (function_two_type, list_elt_type, list_type);
  1976. extern list_type    list_union (list_type, list_type);
  1977. extern list_type    list_multi_union (list_type, list_type);  /* allows for repeats */
  1978.  
  1979. extern int        list_stat (void);
  1980.  
  1981. #define list_copy_1(a) list_copy (list_1 (a))
  1982. #define list_copy_2(a,b) list_copy (list_2 (a,b))
  1983. #define list_copy_unordered_2(a,b) list_copy (list_unordered_2 (a,b))
  1984. #define list_copy_3(a,b,c) list_copy (list_3 (a,b,c))
  1985.  
  1986. /* list_start, list_rest and list_pick are used in tandem to step through
  1987.  * a list.  list_start() returns the beginnging of a list, and list_rest
  1988.  * returns successive elements in the list.  A return of NIL indicates end
  1989.  * of list.  Calling list_pick() return the actual element.
  1990.  * for (l = list_start (list); l != NIL; l = list_rest (l)) play_with (list_pick (l));
  1991.  */
  1992. #define list_start(l) (l->next)
  1993. #define list_rest(l) (l->next)
  1994. #define list_pick(l) (l->elt)
  1995. SHAR_EOF
  1996. fi
  1997. if test -f 'main.c'
  1998. then
  1999.     echo shar: "will not over-write existing file 'main.c'"
  2000. else
  2001. cat << \SHAR_EOF > 'main.c'
  2002. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  2003.  
  2004. #include "games.c"
  2005.  
  2006. void main(int argc, char **argv, char **envp_) {
  2007.     char input[MAXBUFF];
  2008.     int i;
  2009.     game_type g;
  2010.     
  2011.     envp = envp_;
  2012.     init();
  2013.     if (argc > 1) { /* run a command for each argument, then output last */
  2014.         for (i = 1; i < argc; i++) {
  2015.             strcpy (input, argv[i]);
  2016.             strcat (input, "\n");
  2017.             g = game_parse (input);
  2018.             }
  2019.         game_printf (g);
  2020.     } else games();
  2021. }
  2022.  
  2023. SHAR_EOF
  2024. fi
  2025. if test -f 'operations.c'
  2026. then
  2027.     echo shar: "will not over-write existing file 'operations.c'"
  2028. else
  2029. cat << \SHAR_EOF > 'operations.c'
  2030. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  2031.  
  2032. /* Kluges for kos (not well thought out -- certainly unproven)
  2033.  * are marked with the comment *KLUGED KO* */
  2034.  
  2035. #include "externs.h"
  2036. #include "rational.h"
  2037. #include "list.h"
  2038. #include "hash.h"
  2039. #include "operations.h"
  2040. #include "output.h"
  2041. #include "corridors.h"
  2042.  
  2043. #define GNIL ((game_cell_type) 0)
  2044. #define nusb(n,u,s,k) num_up_star_babyko(n,u,s,k)
  2045. #define is_nusb(g) is_num_up_star_babyko(g)
  2046.  
  2047. game_type        saltus;
  2048. int            period;
  2049. game_cell_type        game_cell[MAX_GAMES];    /* array of pointers to game cells */
  2050. static unsigned long    game_cells = 0;        /* Total number of game cells used */
  2051. static game_cell_type    game_free_list = GNIL;
  2052. static Q_type        frozen_temperature;
  2053. static game_type    unit;
  2054. static list_type    unit_adder = NIL, unit_neg_adder = NIL;
  2055. static int        _rstar_;
  2056.  
  2057. game_type zero;
  2058. game_type one;
  2059. game_type two;
  2060. game_type neg1;
  2061. game_type one_star;
  2062. game_type ko;
  2063. game_type kobar;
  2064. game_type babyko;
  2065. game_type babykobar;
  2066. var_type  dummy_var;    /* set_var shouldn't make game point to variable */
  2067.  
  2068. static void game_free_cell (game_cell_type cell) {
  2069.     cell -> next = game_free_list;
  2070.     game_free_list = cell;
  2071.     return;
  2072. }
  2073.  
  2074. static void game_free (game_type g) {
  2075.     list_free (game_cell[g]->left);
  2076.     list_free (game_cell[g]->right);
  2077.     game_free_cell (game_cell[g]);
  2078.     if (g == game_cells) game_cells--;
  2079.     return;
  2080. }
  2081.  
  2082. static game_cell_type game_get_cell (void) {
  2083.     game_cell_type cell, p;
  2084.     unsigned i;
  2085.     
  2086.     if (game_free_list == GNIL) {
  2087.         if (!(game_free_list = (game_cell_type)
  2088.               malloc (GAME_BLOCK_SIZE * sizeof (struct game_struct))))
  2089.             myerror ("game_get_cell: malloc couldn't free block");
  2090.         for (i = 1, p=game_free_list; i < GAME_BLOCK_SIZE; i++, p++)
  2091.             p->next = p+1;
  2092.         p->next = GNIL;
  2093.     }
  2094.     cell = game_free_list;
  2095.     game_free_list = game_free_list->next;
  2096.     return cell;
  2097. }
  2098.  
  2099. static game_type new_game ()
  2100. {
  2101.     if (++game_cells >= MAX_GAMES) {
  2102.         myerror ("new_game: No more games.  Sorry.");
  2103.         exit (1);
  2104.     }
  2105.     game_cell[game_cells] = game_get_cell();
  2106.     game_cell[game_cells]->left = NIL;
  2107.     game_cell[game_cells]->right = NIL;
  2108.     game_cell[game_cells]->flags = 0;
  2109.     game_cell[game_cells]->Num = Q_0;
  2110.     game_cell[game_cells]->Star = 0;
  2111.     game_cell[game_cells]->Up = 0;
  2112.     game_cell[game_cells]->var = NIL;
  2113.     game_cell[game_cells]->next = GNIL;
  2114.     return (game_type) game_cells;
  2115. }
  2116.  
  2117. static game_type dominates (list_type list, game_type g, test_type test) {
  2118.     list_type l;
  2119.     
  2120.     for (l = list_start (list); l != NIL; l = list_rest (l))
  2121.         if ((* test) (list_pick (l), g)) return list_pick (l);
  2122.     return (game_type) FALSE;
  2123. }
  2124.  
  2125.  
  2126. static void reverse_reversals (game_type g) {
  2127.     game_type h;
  2128.     list_type l;
  2129.     list_type l2;
  2130.     
  2131.     for (l = list_start (left_options (g)); l != NIL;) {
  2132.         h = dominates (right_options (list_pick (l)), g, le);
  2133.         if (h) {
  2134.             list_delete (left_options (g), list_pick (l));
  2135.             for (l2 = list_start (extended_left_options (h)); l2 != NIL; l2 = list_rest (l2))
  2136.                 list_insert (left_options (g), list_pick(l2));
  2137.             l = list_start (left_options (g));
  2138.         }
  2139.         else
  2140.             l = list_rest (l);
  2141.     }
  2142.     for (l = list_start (right_options (g)); l != NIL;) {
  2143.         h = dominates (left_options (list_pick (l)), g, ge);
  2144.         if (h) {
  2145.             list_delete (right_options (g), list_pick (l));
  2146.             for (l2 = list_start (extended_right_options (h)); l2 != NIL; l2 = list_rest (l2))
  2147.                 list_insert (right_options (g), list_pick (l2));
  2148.             l = list_start (right_options (g));
  2149.         }
  2150.         else
  2151.             l = list_rest (l);
  2152.     }
  2153.     return;
  2154. }
  2155.  
  2156. static void remove_dominated_options (list_type list, test_type test) {
  2157.     list_type list2, l, l2;
  2158.     game_type g, h;
  2159.  
  2160.     list2 = list_make();
  2161.     for (l = list_start (list); l != NIL; l = list_rest (l))
  2162.         if (! (dominates (list2, g = list_pick (l), test))) {
  2163.             for (l2 = list_start (list2); l2 != NIL;) {
  2164.                 h = list_pick (l2);
  2165.                 l2 = list_rest (l2);
  2166.                 if ((* test) (g, h))
  2167.                     list_delete (list2, h);
  2168.             }
  2169.             list_insert (list2, g);
  2170.         }
  2171.     list_clobber (list, list2);
  2172. }
  2173.  
  2174. static void evaluate (game_type g) {
  2175.     game_type l1, l2, l3, r1, r2, r3, h;
  2176.     int ls, rs;
  2177.     int maxlstar = -1, maxrstar = -1;
  2178.     Q_type n;
  2179.     int k;
  2180.     boolean is_num_equal = TRUE;
  2181.     boolean is_all_num_star_babyko = TRUE;
  2182.     boolean can_evaluate = TRUE;
  2183.     list_type l;
  2184.     
  2185.     ls = count_left_options (g);
  2186.     rs = count_right_options (g);
  2187.     l1 = ls >= 1 ? list_nth (left_options (g), 1) : FALSE;
  2188.     l2 = ls >= 2 ? list_nth (left_options (g), 2) : FALSE;
  2189.     l3 = ls >= 3 ? list_nth (left_options (g), 3) : FALSE;
  2190.     r1 = rs >= 1 ? list_nth (right_options (g), 1) : FALSE;
  2191.     r2 = rs >= 2 ? list_nth (right_options (g), 2) : FALSE;
  2192.     r3 = rs >= 3 ? list_nth (right_options (g), 3) : FALSE;
  2193.     n = l1 ? num_value (l1) : r1 ? num_value (r1) : Q_0;
  2194.     k = l1 ? babyko_value (l1) : r1 ? babyko_value (r1) : 0;
  2195.     for (l = list_start (left_options (g)); l != NIL; l = list_rest (l)) {
  2196.         h = list_pick (l);
  2197.         if (!Q_eq (num_value (h), n)) is_num_equal = FALSE;
  2198.         if (babyko_value (g) != k) can_evaluate = FALSE;
  2199.         if (!is_num_star_babyko (h)) is_all_num_star_babyko = FALSE;
  2200.         else if (star_value(h) > maxlstar) maxlstar = star_value (h);
  2201.         if (!is_evaluated (h)) can_evaluate = FALSE;
  2202.         if (has_ko (h)) set_flag (g, HAS_KO_FLAG);
  2203.     }
  2204.     for (l = list_start (right_options (g)); l != NIL; l = list_rest (l)) {
  2205.         h = list_pick (l);
  2206.         if (!Q_eq (num_value (h), n)) is_num_equal = FALSE;
  2207.         if (babyko_value (g) != k) can_evaluate = FALSE;
  2208.         if (!is_num_star_babyko (h)) is_all_num_star_babyko = FALSE;
  2209.         else if (star_value (h) > maxrstar) maxrstar = star_value (h);
  2210.         if (!is_evaluated (h)) can_evaluate = FALSE;
  2211.         if (has_ko (h)) set_flag (g, HAS_KO_FLAG);
  2212.     }
  2213.     if (!can_evaluate) return;
  2214.     else if (!l1 && !r1) nusb (Q_0,0,0,0);
  2215.     else if (!r1) nusb (Q_plus (n, Q_1),0,0,0);
  2216.     else if (!l1) nusb (Q_minus (n, Q_1),0,0,0);
  2217.     else if (is_num (l1) && is_num (r1) && !l2 && !r2)
  2218.         if (Q_lt (num_value (l1), num_value (r1)))
  2219.             nusb (Q_divide (Q_plus (num_value (l1), num_value (r1)),Q_2),0,0,k);
  2220.         else if (is_num_equal) nusb (n,0,1,k);
  2221.         else;
  2222.     else if (!is_num_equal) return;
  2223.     else if (l2 || r2)
  2224.         if (is_num_babyko(r1) && !r2 && !l3
  2225.             && (   (is_num_star_babyko(l1) && star_value(l1) == 1 && is_num_babyko(l2))
  2226.             || (is_num_star_babyko(l2) && star_value(l2) == 1 && is_num_babyko(l1))))
  2227.             nusb (n,1,1,k);
  2228.         else if (is_num_babyko(l1) && !l2 && !r3
  2229.              && (   (is_num_star_babyko(r1) && star_value(r1) == 1 && is_num_babyko(r2))
  2230.                  || (is_num_star_babyko (r2) && star_value(r2) == 1 && is_num_babyko(r1))))
  2231.             nusb (n,-1,1,k);
  2232.         else if (is_all_num_star_babyko && ls == rs
  2233.              && maxlstar == (ls - 1) && maxrstar == (rs - 1))
  2234.             nusb (n,0,ls,k);
  2235.         else;
  2236.     else if (is_num_babyko (l1) && !l2 && is_nusb (r1) && !r2 && (up_value (r1) >= 0))
  2237.         nusb (n, up_value(r1)+1, star_value(r1)^1,k);
  2238.     else if (is_num_babyko (r1) && !r2 && is_nusb (l1) && !l2 && (up_value (l1) <= 0))
  2239.         nusb (n, up_value(l1)-1, star_value(l1)^1,k);
  2240.     return;
  2241. }
  2242.  
  2243. static game_type simplify (game_type g) {
  2244.     list_type l;
  2245.  
  2246.     remove_dominated_options (left_options (g), ge);
  2247.     remove_dominated_options (right_options (g), le);
  2248.     for (l = list_start (left_options (g)); l != NIL; l = list_rest (l))
  2249.         if (has_ko (list_pick (l))) set_flag (g, HAS_KO_FLAG);
  2250.     for (l = list_start (right_options (g)); l != NIL; l = list_rest (l))
  2251.         if (has_ko (list_pick (l))) set_flag (g, HAS_KO_FLAG);
  2252.     reverse_reversals (g);
  2253.     clear_flag (g, HAS_KO_FLAG);
  2254.     remove_dominated_options (left_options (g), ge);
  2255.     remove_dominated_options (right_options (g), le);
  2256.     l = list_combine (left_options (g), right_options (g));
  2257.     if (hash_test (SIMPLIFY_KEY, l)) {
  2258.         game_free (g);
  2259.         g = hash_get_last();
  2260.         list_free (l);
  2261.     } else {
  2262.         hash_put (SIMPLIFY_KEY, l, g);
  2263.         evaluate (g);
  2264.         set_flag (g, CANONICAL_FLAG);
  2265.     }
  2266.     return g;
  2267. }
  2268.  
  2269. static int max_star (game_type g) {
  2270.     list_type l;
  2271.     int n = 0, s;
  2272.     if (is_num_up_star (g))
  2273.         if (up_value (g) == 0) return star_value (g);
  2274.         else return (1 | star_value (g));
  2275.      for (l = list_start (left_options (g)); l != NIL; l = list_rest (l)) {
  2276.         s = max_star (list_pick (l));
  2277.         n = (n >= s ? n : s);
  2278.     }
  2279.     for (l = list_start (right_options (g)); l != NIL; l = list_rest (l)) {
  2280.         s = max_star (list_pick (l));
  2281.         n = (n >= s ? n : s);
  2282.     }
  2283.     return n;
  2284. }
  2285.  
  2286. game_type num_up_star_babyko (Q_type n, int u, int s, int k) {
  2287.     game_type g;
  2288.     list_type l, args;
  2289.     
  2290.     if (s < 0) s = -s;
  2291.     args = list_copy_3 (u,s,k);
  2292.     list_insert_unsorted (args, Q_p(n));
  2293.     list_insert_unsorted (args, Q_q(n));
  2294.     if (hash_test (NUM_UP_STAR_BABYKO_KEY, args)) {
  2295.         list_free (args);
  2296.         return hash_get_last();
  2297.     }
  2298.     if (u == 0 && s == 0) {        /* numbers */
  2299.         if (k == 0 || !Q_is_int (n))
  2300.             g = make_canonical ((!Q_is_int(n) || Q_gt(n,Q_0))        /* left */
  2301.                         ? list_copy_1 (nusb (Q (Q_p(n)-1, Q_q(n)),0,0,k))
  2302.                         : list_make()
  2303.                         ,
  2304.                         (!Q_is_int(n) || Q_lt (n, Q_0))         /* right */
  2305.                         ? list_copy_1 (nusb (Q (Q_p(n)+1, Q_q(n)),0,0,k))
  2306.                         : list_make());
  2307.         else if (Q_is_int (n)) g = int_babyko (Q_p(n), k);
  2308.     } else if (u == 0) {                    /* num + star */
  2309.         g = nusb (n, 0, s-1, k);
  2310.         if (s > 1) l = list_copy (left_options (g));
  2311.         else l = list_make();
  2312.         list_insert (l, g);
  2313.         g = make_canonical (l, list_copy (l));
  2314.     } else if (u > 0) {
  2315.         if (u == 1 && s == 1)
  2316.             g = make_canonical (list_copy_2 (nusb (n,0,0,k), nusb (n,0,1,k)),
  2317.                         list_copy_1 (nusb (n,0,0,k)));
  2318.         else g = make_canonical (list_copy_1 (nusb (n,0,0,k)),
  2319.                      list_copy_1 (nusb (n,u-1,s^1,k)));
  2320.     } else /* if (u < 0) */ {
  2321.         if (u == -1 && s == 1)
  2322.             g = make_canonical (list_copy_1 (nusb (n,0,0,k)),
  2323.                         list_copy_2 (nusb (n,0,0,k), nusb (n,0,1,k)));
  2324.         else g = make_canonical (list_copy_1 (nusb (n,u+1,s^1,k)),
  2325.                      list_copy_1 (nusb (n,0,0,k)));
  2326.     }
  2327.     set_flag (g, NUSB_FLAG);
  2328.     game_cell[g]->Num = n;
  2329.     game_cell[g]->Up = u;
  2330.     game_cell[g]->Star = s;
  2331.     if (k != 0) {
  2332.         set_flag (g, HAS_KO_FLAG);
  2333.         set_flag (g, k == 1 ? BABYKO_FLAG : BABYKOBAR_FLAG);
  2334.     }
  2335.     hash_put (NUM_UP_STAR_BABYKO_KEY, args, g);
  2336.     return g;
  2337. }
  2338.  
  2339. game_type int_ko_star (int n, int k, int s) {
  2340.     game_type g, h;
  2341.     int i;
  2342.  
  2343.     if (s < 0) return int_ko_star (n, k, -s);
  2344.     else if (k > 1) return int_ko_star (n+1, k-3, s);
  2345.     else if (k < -1) return int_ko_star (n-1, k+3, s);
  2346.     else if (k == 0) return num_up_star (Q_int (n), 0, s);
  2347.     if (hash_test (INT_KO_STAR_KEY, list_3 (n, k, s)))
  2348.         return hash_get_last();
  2349.     i = (k == 1 ? n : n-1);
  2350.     g = new_game();
  2351.     h = new_game();
  2352.  
  2353.     game_cell[g]->left = list_copy_1 (h);
  2354.     game_cell[g]->right = list_copy_1 (plus (g_int (i), star(s)));
  2355.     game_cell[g]->Num = Q_int (i);
  2356.     game_cell[g]->Star = s;
  2357.     set_flag (g, CANONICAL_FLAG);
  2358.     set_flag (g, KO_FLAG);
  2359.     set_flag (g, HAS_KO_FLAG);
  2360.  
  2361.     game_cell[h]->left = list_copy_1 (plus (g_int (i+1), star(s)));
  2362.     game_cell[h]->right = list_copy_1 (g);
  2363.     game_cell[h]->Num = Q_int (i+1);
  2364.     game_cell[h]->Star = s;
  2365.     set_flag (h, CANONICAL_FLAG);
  2366.     set_flag (h, KOBAR_FLAG);
  2367.     set_flag (h, HAS_KO_FLAG);
  2368.  
  2369.     hash_put (INT_KO_STAR_KEY, list_copy_3 (i, 1, s), g);
  2370.     hash_put (INT_KO_STAR_KEY, list_copy_3 (i+1, -1, s), h);
  2371.     if (k == 1) return g;
  2372.     else return h;
  2373. }
  2374.  
  2375. game_type int_babyko (int n, int k) {
  2376.     game_type g, h;
  2377.     if (k > 1) return int_babyko (n+1, k-3);
  2378.     else if (k < -1) return int_babyko (n-1, k+3);
  2379.     else if (k == 0) return g_int (n);
  2380.     if (hash_test (INT_BABYKO_KEY, list_2 (n, k)))
  2381.         return hash_get_last();
  2382.     g = new_game();
  2383.     h = new_game();
  2384.  
  2385.     game_cell[g]->left = list_copy_1 (h);
  2386.     game_cell[g]->right = list_copy_1 (g_int (n+1));
  2387.     game_cell[g]->Num = Q_int (n);
  2388.     set_flag (g, CANONICAL_FLAG);
  2389.     set_flag (g, NUSB_FLAG);
  2390.     set_flag (g, BABYKO_FLAG);
  2391.     set_flag (g, HAS_KO_FLAG);
  2392.  
  2393.     game_cell[h]->left = list_copy_1 (g_int (n-1));
  2394.     game_cell[h]->right = list_copy_1 (g);
  2395.     game_cell[h]->Num = Q_int (n);
  2396.     set_flag (h, CANONICAL_FLAG);
  2397.     set_flag (h, NUSB_FLAG);
  2398.     set_flag (h, BABYKOBAR_FLAG);
  2399.     set_flag (h, HAS_KO_FLAG);
  2400.  
  2401.     hash_put (INT_BABYKO_KEY, list_copy_2 (n,  1), g);
  2402.     hash_put (INT_BABYKO_KEY, list_copy_2 (n, -1), h);
  2403.     if (k == 1) return g;
  2404.     else return h;
  2405. }
  2406.     
  2407. void init (void) {
  2408.     list_init();
  2409.     hash_init();
  2410.     zero = make(list_make(), list_make());
  2411.     one = g_int (1);
  2412.     two = g_int (2);
  2413.     neg1 = g_int (-1);
  2414.     one_star = plus (g_int (1), star (1));
  2415.     ko = int_ko_star (0,1,0);
  2416.     kobar = int_ko_star (0,-1,0);
  2417.     babyko = int_babyko (0,1);
  2418.     babykobar = int_babyko (0,-1);
  2419.     mult (zero, one_star);
  2420.     heat (zero, one);
  2421.     overheat (zero, one_star, one);
  2422.     strcpy (chill_string, "g[1]\n");
  2423.     strcpy (warm_string, "g.1*\n");
  2424.     dummy_var = list_0;
  2425.     period = 2;
  2426.     saltus = zero;
  2427. }
  2428.  
  2429. void game_clear (void)
  2430. {
  2431.     game_type g;
  2432.  
  2433.     for (g = game_cells; g >= 1; g--)
  2434.         game_free (g);
  2435.     list_free (unit_neg_adder);
  2436.     list_free (unit_adder);
  2437.     unit_adder = unit_neg_adder = NIL;
  2438. }
  2439.  
  2440. void reinit (void) {
  2441.     hash_clear(UNEXPENDABLE_KEYS | EXPENDABLE_KEYS | OTHER_KEYS, 100);
  2442.     corridor_clear();
  2443.     game_clear();
  2444.     zero = make(list_make(), list_make());
  2445.     one = g_int (1);
  2446.     two = g_int (2);
  2447.     neg1 = g_int (-1);
  2448.     one_star = plus (g_int (1), star (1));
  2449.     ko = int_ko_star (0,1,0);
  2450.     kobar = int_ko_star (0,-1,0);
  2451.     babyko = int_babyko (0,1);
  2452.     babykobar = int_babyko (0,-1);
  2453.     mult (zero, one_star);
  2454.     heat (zero, one);
  2455.     overheat (zero, one_star, one);
  2456. }
  2457.  
  2458. void clean (void) {
  2459.     hash_clear (EXPENDABLE_KEYS | OTHER_KEYS, 100);
  2460.     corridor_clear();
  2461. }    
  2462.  
  2463. game_type make (list_type left, list_type right) {
  2464.     game_type g;
  2465.  
  2466.     g = new_game();
  2467.     game_cell[g]->left = left;
  2468.     game_cell[g]->right = right;
  2469.     g = simplify(g);
  2470.     return g;
  2471. }
  2472.  
  2473. game_type make_canonical (list_type left, list_type right) {
  2474.     game_type g;
  2475.     list_type l;
  2476.  
  2477.     l = list_combine (left, right);
  2478.     if (hash_test (SIMPLIFY_KEY, l)) {
  2479.         g = hash_get_last();
  2480.         list_free (l);
  2481.         list_free (left);
  2482.         list_free (right);
  2483.     } else {
  2484.         g = new_game();
  2485.         game_cell[g]->left = left;
  2486.         game_cell[g]->right = right;
  2487.         set_flag (g, CANONICAL_FLAG);
  2488.         hash_put (SIMPLIFY_KEY, l, g);
  2489.     }
  2490.     return g;
  2491. }
  2492.  
  2493. boolean is_var (game_type g) {
  2494.     var_type v;
  2495.  
  2496.     v = game_cell[g]->var;
  2497.     if (v == NIL) return FALSE;
  2498.     if (eq (get_var (v), g)) return TRUE;
  2499.     else {
  2500.         list_free (v);
  2501.         game_cell[g]->var = NIL;
  2502.         return FALSE;
  2503.     }
  2504. }
  2505.  
  2506. boolean is_tiny (game_type g) {
  2507.     game_type h;
  2508.     return (count_left_options (g) == 1
  2509.         && count_right_options (g) == 1
  2510.         && eq (nth_left_option (g, 1), zero)
  2511.         && (h = nth_right_option (g, 1), TRUE)
  2512.         && count_left_options (h) == 1
  2513.         && count_right_options (h) == 1
  2514.         && eq (nth_left_option (h, 1), zero)
  2515.         && lt (nth_right_option (h, 1), zero));
  2516. }
  2517. boolean is_miny (game_type g) {return is_tiny (negative (g));}
  2518.  
  2519. static int on_exponent_ (game_type g) {
  2520.     game_type h;
  2521.     int i;
  2522.  
  2523.     if (count_left_options (g) != 1 || count_right_options (g) != 1) return 0;
  2524.     h = nth_right_option (g, 1);
  2525.     g = nth_left_option (g, 1);
  2526.     for (i = 1;; i++) {
  2527.         if (eq (g, zero)) return i;
  2528.         if (count_left_options (g) != 1 || count_right_options (g) != 1) return 0;
  2529.         if (!eq (h, nth_right_option (g, 1))) return 0;
  2530.         g = nth_left_option (g, 1);
  2531.     }
  2532. }
  2533.  
  2534. boolean is_on (game_type g) {return (on_exponent (g) > 1) && !is_nusb(g);}
  2535. int on_exponent (game_type g) {
  2536.     int i;
  2537.  
  2538.     if ((i = on_exponent_ (g)) > 0) return i;
  2539.     else return on_exponent_ (negative (g));
  2540. }
  2541.  
  2542. game_type on_value (game_type g) {
  2543.     if (on_exponent_ (g) > 1) return vs (zero, nth_right_option (g, 1));
  2544.     else if (on_exponent_ (g) < 1) return negative (on_value (negative (g)));
  2545.     else return g;
  2546. }
  2547.  
  2548. boolean is_off (g) game_type g; {return is_on (negative (g));}
  2549.  
  2550. game_type tiny_value(game_type g) {g=minus (g, num (mean (g)));
  2551.   return negative (nth_right_option(nth_right_option (g,1),1));}
  2552. game_type miny_value(game_type g) {g=minus (g, num (mean(g)));
  2553.   return nth_left_option (nth_left_option (g,1),1);}
  2554. var_type var_value (game_type g) {return is_var(g) ? game_cell[g]->var : NO_GAME;}
  2555. int ko_value (game_type g) {return _flags(g)&KO_FLAG ? 1 : _flags(g)&KOBAR_FLAG ? -1 : 0;}
  2556. int babyko_value (game_type g) {return _flags(g)&BABYKO_FLAG ? 1 : _flags(g)&BABYKOBAR_FLAG ? -1 : 0;}
  2557.  
  2558. boolean is_canonical(game_type g) {return _flags(g) & CANONICAL_FLAG;}
  2559. boolean is_evaluated(game_type g) {return _flags(g) & EVALUATED_FLAG;}
  2560. boolean is_int(game_type g) {return is_num (g) && Q_is_int (num_value (g));}
  2561. boolean is_num(game_type g) {return is_num_star (g) && star_value (g) == 0;}
  2562. boolean is_up(game_type g) {return is_up_star (g) && star_value (g) == 0;}
  2563. boolean is_star(game_type g) {return is_up_star (g) && up_value (g) == 0;}
  2564. boolean is_num_up_star(game_type g) {return is_nusb(g)&&!babyko_value(g);}
  2565. boolean is_num_star(game_type g) {return is_num_up_star (g) && up_value (g) == 0;}
  2566. boolean is_num_up(game_type g) {return is_num_up_star (g) && star_value (g) == 0;}
  2567. boolean is_up_star(game_type g) {return is_num_up_star(g) && Q_eq (num_value (g), Q_0);}
  2568. boolean is_int_ko_star(game_type g) {return (is_num_star(g)&&Q_is_int(num_value(g))&&star_value(g)<=1) || ko_value(g);}
  2569. boolean is_int_ko(game_type g) {return (is_int_ko_star(g) && star_value (g) == 0);}
  2570. boolean is_num_up_star_babyko (game_type g) {return _flags (g) & NUSB_FLAG;}
  2571. boolean is_num_star_babyko (game_type g) {return is_nusb (g) && up_value (g) == 0;}
  2572. boolean is_num_babyko (game_type g) {return is_num_star_babyko (g) && star_value (g) == 0;}
  2573. boolean is_int_babyko(game_type g) {return is_num_babyko (g) && Q_is_int (num_value (g));}
  2574. boolean has_ko(game_type g) {return _flags (g) & HAS_KO_FLAG;}
  2575.     
  2576. char *var_sprintn (char *s, var_type v, int n) {
  2577.     list_type l;
  2578.     char *t;
  2579.  
  2580.     t = s;
  2581.     for (l = list_start (v); l != NIL && n > 0; l = list_rest(l), s++, n--)
  2582.         *s = list_pick (l) & 255;
  2583.     *s = '\0';
  2584.     return t;
  2585. }
  2586.  
  2587. game_type plus (game_type g, game_type h) {
  2588.     list_type l1, l2, left, right;
  2589.     game_type result;
  2590.  
  2591.     if (is_nusb (g) && is_nusb (h))
  2592.         return nusb (Q_plus (num_value (g), num_value (h)),
  2593.                  up_value (g) + up_value (h),
  2594.                  star_value (g) ^ star_value (h),
  2595.                  babyko_value (g) + babyko_value (h));
  2596.     else if (eq (g, zero)) return h;
  2597.     else if (eq (h, zero)) return g;
  2598.     else if (is_int_ko_star (g) && is_int_ko_star (h))        /*KLUGED KO*/
  2599.         return int_ko_star (int_value (g) + int_value (h),
  2600.                     ko_value (g) + ko_value (h),
  2601.                     star_value (g) ^ star_value (h));
  2602.     if (hash_test (PLUS_KEY, list_unordered_2(g,h)))
  2603.         return hash_get_last ();
  2604.     if (is_num (g) || (is_int_ko_star (g) && has_ko (g)))        /*KLUGED KO*/
  2605.         result = make (list_mapcl (plus, g, left_options (h)),
  2606.                    list_mapcl (plus, g, right_options (h)));
  2607.     else if (is_num (h) || (is_int_ko_star (h) && has_ko (h)))    /*KLUGED KO*/
  2608.         result = make (list_maplc (plus, left_options (g), h),
  2609.                    list_maplc (plus, right_options (g), h));
  2610.     else {
  2611.         l1 = list_maplc (plus, left_options (g), h);
  2612.         l2 = list_mapcl (plus, g, left_options (h));
  2613.         left = list_union (l1, l2);
  2614.         list_free (l1);
  2615.         list_free (l2);
  2616.         l1 = list_maplc (plus, right_options (g), h);
  2617.         l2 = list_mapcl (plus, g, right_options (h));
  2618.         right = list_union (l1, l2);
  2619.         list_free (l1);
  2620.         list_free (l2);
  2621.         result = make (left, right);
  2622.     }
  2623.     hash_put (PLUS_KEY, list_copy_unordered_2(g,h), result);
  2624.     return result;
  2625. }
  2626.  
  2627.  
  2628. game_type negative (game_type g) {
  2629.     game_type result;
  2630.  
  2631.     if (is_nusb (g))                /*KLUGED KO*/
  2632.         return nusb (Q_negative (num_value (g)), - up_value (g),
  2633.                  star_value (g), - babyko_value (g));
  2634.     else if (is_int_ko_star (g))            /*KLUGED KO*/
  2635.         return int_ko_star (- int_value (g), - ko_value (g), star_value (g));
  2636.     if (hash_test (NEGATIVE_KEY, list_1(g)))
  2637.         result = hash_get_last();
  2638.     else {
  2639.         result = make (list_map (negative, right_options (g)),
  2640.                    list_map (negative, left_options (g)));
  2641.         hash_put (NEGATIVE_KEY, list_copy_1(g), result);
  2642.     }
  2643.     return result;
  2644. }
  2645.  
  2646. game_type minus (game_type g, game_type h) {
  2647.     return plus (g, negative (h));
  2648. }
  2649.  
  2650. game_type times (int n, game_type g) {
  2651.     if (n == 0) return zero;
  2652.     else if (n < 0) return times (-n, negative (g));
  2653.     else return plus (g, times (n-1, g));
  2654. }
  2655.  
  2656. boolean ge (game_type g, game_type h) {
  2657.     list_type l, r;
  2658.     boolean result = TRUE;
  2659.     int t;
  2660.     game_type d, gr, hl;
  2661.  
  2662.     if (eq (g, h)) return TRUE;
  2663.     else if (is_nusb (g) && is_nusb (h)) {
  2664.         d = minus (g, h);
  2665.         if (babyko_value (d) == -1)
  2666.             d = minus (d, num (Q (1,2)));    /* 0 <= k <= 1/2 */
  2667.         if      (Q_gt (num_value (d), Q_0)) return TRUE;
  2668.         else if (Q_lt (num_value (d), Q_0)) return FALSE;
  2669.         else if ((t = up_value (d)) < 0) return FALSE;
  2670.         else if (t >= 2) return TRUE;
  2671.         else if (t == 1) return star_value (d) != 1;
  2672.         else return star_value (d) == 0;
  2673.     } else if (is_num (h) && !has_ko (g)) {
  2674.         for (l = list_start (right_options (g)); l != NIL; l = list_rest(l))
  2675.             if (ge (h, list_pick (l))) return FALSE;
  2676.         return TRUE;
  2677.     } else if (is_num (g) && !has_ko (h)) {
  2678.         for (l = list_start (left_options (h)); l != NIL; l = list_rest(l))
  2679.             if (ge (list_pick (l), g))
  2680.                 return FALSE;
  2681.         return TRUE;
  2682.     } else if (is_int_ko_star (g) && is_int_ko_star (h)) {
  2683.         d = minus (g, h);
  2684.         return (int_value (d) > 0 || eq (d, zero) || eq (d, int_ko_star (0,1,1)));
  2685.     } else if (hash_test (GE_KEY, list_2(g,h)))
  2686.         return  (boolean) hash_get_last();
  2687.     if (has_ko (g) || has_ko (h)) {        /*KLUGED KO*/
  2688.         for (r = list_start (right_options (g));
  2689.              r != NIL; r = list_rest (r)) {
  2690.             t = FALSE;
  2691.             gr = list_pick (r);
  2692.             for (l=list_start(extended_left_options(gr)); l!=NIL; l=list_rest(l))
  2693.                 if (ge (list_pick (l), h)) {t = TRUE; break;}
  2694.             if (!t)    for (l=list_start(extended_right_options(h)); l!=NIL; l=list_rest(l))
  2695.                 if (ge (gr, list_pick (l))) {t = TRUE; break;}
  2696.             if (!t) {result = FALSE; break;}
  2697.         }
  2698.         if (result) for (r = list_start (left_options (h));
  2699.                  r != NIL; r = list_rest (r)) {
  2700.             t = FALSE;
  2701.             hl = list_pick (r);
  2702.             for (l=list_start(extended_right_options(hl)); l!=NIL; l=list_rest(l))
  2703.                 if (ge (g, list_pick (l))) {t = TRUE; break;}
  2704.             if (!t) for (l=list_start(extended_left_options(g)); l!=NIL; l=list_rest(l))
  2705.                 if (ge (list_pick (l), hl)) {t = TRUE; break;}
  2706.             if (!t) {result = FALSE; break;}
  2707.         }
  2708.     } else {
  2709.         for (l = list_start (left_options (h)); l != NIL; l = list_rest(l))
  2710.             if (ge (list_pick (l), g)) {result = FALSE; break;}
  2711.         if (result) for (l = list_start (right_options (g)); l != NIL; l = list_rest(l))
  2712.             if (ge (h, list_pick (l))) {result = FALSE; break;}
  2713.     }
  2714.     if (is_canonical (g) && is_canonical (h))
  2715.         hash_put (GE_KEY, list_copy_2(g,h), (int) result);
  2716.     return result;
  2717. }
  2718. boolean le(game_type g, game_type h) {return (ge (h, g));}
  2719. boolean eq(game_type g, game_type h) {return g == h;}
  2720. boolean gt(game_type g, game_type h) {return g != h && ge(g,h);}
  2721. boolean lt(game_type g, game_type h) {return g != h && ge(h,g);}
  2722.  
  2723.  
  2724. char *compare (game_type g, game_type h) {
  2725.     boolean a, b;
  2726.     a = ge (g, h);
  2727.     b = le (g, h);
  2728.     if (a && b) return "=";
  2729.     else if (a && !b) return ">";
  2730.     else if (!a && b) return "<";
  2731.     else return "<>";
  2732. }
  2733.  
  2734. boolean lmove_ok (game_type g, game_type h) {
  2735.     list_type l;
  2736.     for (l = list_start (left_options (g)); l != NIL; l = list_rest (l))
  2737.         if (ge (h, list_pick (l))) return TRUE;
  2738.     return FALSE;
  2739. }
  2740.  
  2741. boolean rmove_ok (game_type g, game_type h) {
  2742.     list_type l;
  2743.     for (l = list_start (right_options (g)); l != NIL; l = list_rest (l))
  2744.         if (le (h, list_pick (l))) return TRUE;
  2745.     return FALSE;
  2746. }
  2747.  
  2748.  
  2749. Q_type left_stop (game_type g) {
  2750.     Q_type n, m;
  2751.     list_type l;
  2752.  
  2753.     if (is_evaluated (g)) return num_value (g);
  2754.     l = list_start (left_options (g));
  2755.     if (l == NIL) return Q_minus (right_stop (g), Q_1);    /*KLUGED KO*/
  2756.     else n = right_stop (list_pick (l));
  2757.     while ((l = list_rest (l)) != NIL) {
  2758.         m = right_stop (list_pick (l));
  2759.         n = (Q_gt (m, n) ? m : n);
  2760.     }
  2761.     return n;
  2762. }
  2763.  
  2764. Q_type right_stop (game_type g) {
  2765.     Q_type n, m;
  2766.     list_type l;
  2767.  
  2768.     if (is_evaluated (g)) return num_value (g);
  2769.     l = list_start (right_options (g));
  2770.     if (l == NIL) return Q_plus (left_stop (g), Q_1);    /*KLUGED KO*/
  2771.     n = left_stop (list_pick (l));
  2772.     while ((l = list_rest (l)) != NIL) {
  2773.         m = left_stop (list_pick (l));
  2774.         n = (Q_lt (m, n) ? m : n);
  2775.     }
  2776.     return n;
  2777. }
  2778.  
  2779. list_type incentives (game_type g) {
  2780.     list_type l1, l2, l3;
  2781.  
  2782.     l1 = left_incentives (g);
  2783.     l2 = right_incentives (g);
  2784.     l3 = list_union (l1, l2);
  2785.     remove_dominated_options (l3, ge);
  2786.     list_free (l1);
  2787.     list_free (l2);
  2788.     return l3;
  2789. }
  2790.     
  2791. list_type left_incentives (game_type g) {return is_int(g) ? list_copy_1 (neg1) : list_maplc (minus, left_options (g), g);}
  2792. list_type right_incentives (game_type g) {return is_int(g) ? list_copy_1 (neg1) : list_mapcl (minus, g, right_options (g));}
  2793.  
  2794. game_type cool (game_type g, Q_type n) {
  2795.     Q_type low, high, try;
  2796.     list_type left, right;
  2797.     list_type l;
  2798.     game_type gtry, h;
  2799.     boolean cold=FALSE;
  2800.     
  2801.     if (is_num (g) || Q_eq (n, Q_0)) {
  2802.         frozen_temperature = Q_0;
  2803.         return g;
  2804.     } else if (is_evaluated (g)) {
  2805.         frozen_temperature = Q_0;
  2806.         h = num (num_value (g));
  2807.         if (ko_value (g) == 0) return h;
  2808.         else return plus (h, ko_value (g) == 1 ? babyko : babykobar);
  2809.     }
  2810.     /* The following code is complicated by the fact that we want */
  2811.     /* to guarantee that the hash table entries are expendable: */
  2812.     /* One of FREEZE_KEY and TEMPERATURE_KEY may have been axed! */
  2813.     else if (hash_test (FREEZE_KEY, list_1 (g))) {
  2814.         h = hash_get_last();
  2815.         if (hash_test (TEMPERATURE_KEY, list_1(g)))
  2816.             if (Q_ge (n, frozen_temperature = num_value (hash_get_last())))
  2817.                 if (Q_eq (n, frozen_temperature)) return h;
  2818.                 else return num (left_stop (h));
  2819.         if (Q_eq (n, Q_infinity)) return num (left_stop (h));
  2820.         hash_delete (FREEZE_KEY, list_1 (g));
  2821.     }
  2822.     if (hash_test (TEMPERATURE_KEY, list_1(g))) hash_delete (TEMPERATURE_KEY, list_1(g));
  2823. #if Q_SIZE == INT_SIZE
  2824.     if (hash_test (COOL_KEY, list_2 (g, n)))
  2825.         return hash_get_last();
  2826. #else
  2827.         if (hash_test (COOL_KEY, list_3 (g, Q_p(n), Q_q(n))))
  2828.                 return hash_get_last();
  2829. #endif
  2830.     if (has_ko (g) && Q_le (left_stop (g), right_stop (g))) cold = TRUE;    /*KLUGED KO*/
  2831.     low = Q_neg1;
  2832.     high = n;
  2833.     try = (Q_eq (high, Q_infinity) ? Q_0 : high);
  2834.     for (;;) {
  2835.         left = list_make();
  2836.         right = list_make();
  2837.         gtry = num (try);
  2838.         
  2839.         for (l = list_start (left_options (g)); l != NIL; l = list_rest (l))
  2840.             list_insert (left, minus (cool (list_pick (l), try), gtry));
  2841.         for (l = list_start (right_options (g)); l != NIL; l = list_rest (l))
  2842.             list_insert (right, plus (cool (list_pick (l), try), gtry));
  2843.         h = make (left, right);
  2844.         if (!is_num (h) && (   Q_le (left_stop (h), right_stop (h)) /* frozen */
  2845.                     || Q_eq (try, n)             /* cooled enough */
  2846.                     || cold)) break;            /*KLUGED KO*/
  2847.         if (is_num (h)) high = try;
  2848.         else low = try;
  2849.         try = Q_simplest_number (low, high);
  2850.     }
  2851.     frozen_temperature = cold ? Q_0 : try;                /*KLUGED KO*/
  2852.     if (Q_eq (left_stop (h), right_stop (h))) {
  2853.         hash_put (FREEZE_KEY, list_copy_1 (g), h);
  2854.         hash_put (TEMPERATURE_KEY, list_copy_1 (g), num (frozen_temperature));
  2855.     } else
  2856. #if Q_SIZE == INT_SIZE
  2857.         hash_put (COOL_KEY, list_copy_2 (g, n), h);
  2858. #else
  2859.         hash_put (COOL_KEY, list_copy_3 (g, Q_p(n), Q_q(n)), h);
  2860. #endif
  2861.     if (Q_gt (n, frozen_temperature)) return num (left_stop (h));
  2862.     else return h;
  2863. }
  2864. Q_type temperature (game_type g) {cool (g, Q_infinity); return frozen_temperature;}
  2865. game_type freeze (game_type g) {return cool (g, temperature (g));}
  2866. Q_type mean (game_type g) {return left_stop (freeze (g));}
  2867.  
  2868. game_type overheat (game_type g, game_type s, game_type t) {
  2869.     list_type left;
  2870.     list_type right;
  2871.     list_type l;
  2872.     game_type h;
  2873.     static game_type last_s, last_t;
  2874.  
  2875.     if (s == NO_GAME) s = last_s; else last_s = s;
  2876.     if (t == NO_GAME) t = last_t; else last_t = t;
  2877.     if (is_int (g)) return times (int_value (g), s);
  2878.     else if (is_int_babyko (g)) return plus (star(1), plus (times (int_value (g), s),    /*KLUGED KO*/
  2879.                                 babyko_value (g) == 1 ? ko : kobar));
  2880.     else if (hash_test (HEAT_KEY, list_3 (g, s, t)))
  2881.         return hash_get_last();
  2882.     left = list_make();
  2883.     right = list_make();
  2884.     for (l = list_start (left_options (g)); l != NIL; l = list_rest (l))
  2885.         list_insert (left, plus (overheat (list_pick (l), s, t), t));
  2886.     for (l = list_start (right_options (g)); l != NIL; l = list_rest (l))
  2887.         list_insert (right, minus (overheat (list_pick (l), s, t), t));
  2888.     h = make (left, right);
  2889.     hash_put (HEAT_KEY, list_copy_3 (g, s, t), h);
  2890.     return h;
  2891. }
  2892.  
  2893. game_type heat (game_type g, game_type t) {
  2894.     list_type left, right, l;
  2895.     game_type h;
  2896.     static game_type last_t;
  2897.  
  2898.     if (t == NO_GAME) t = last_t; else last_t = t;
  2899.     if (is_num (g)) return g;
  2900.     else if (hash_test (HEAT_KEY, list_2 (g, t)))
  2901.         return hash_get_last ();
  2902.     left = list_make();
  2903.     right = list_make();
  2904.     for (l = list_start (left_options (g)); l != NIL; l = list_rest (l))
  2905.         list_insert (left, plus (heat (list_pick (l), t), t));
  2906.     for (l = list_start (right_options (g)); l != NIL; l = list_rest (l))
  2907.         list_insert (right, minus (heat (list_pick (l), t), t));
  2908.     h = make(left, right);
  2909.     hash_put (HEAT_KEY, list_copy_2 (g, t), h);
  2910.     return h;
  2911. }
  2912.  
  2913. game_type _mult (game_type g) {return mult (g, NO_GAME);}
  2914. game_type mult (game_type g, game_type u) {
  2915.     game_type h;
  2916.     list_type l, left, right;
  2917.  
  2918.     if (u != NO_GAME) {
  2919.         unit = u;
  2920.         l = incentives (unit);
  2921.         if (unit_adder != NIL) {
  2922.             list_free (unit_adder);
  2923.             list_free (unit_neg_adder);
  2924.         }
  2925.         unit_adder = list_mapcl (plus, unit, l);
  2926.         unit_neg_adder = list_map (negative, unit_adder);
  2927.         list_free (l);
  2928.     }
  2929.     if (is_int (g)) return times (int_value (g), unit);
  2930.     else if (is_int_babyko (g)) return plus (star (1), plus (times (int_value (g), unit),    /*KLUGED KO*/
  2931.                                  babyko_value (g) == 1 ? ko : kobar));
  2932.     else if (hash_test (MULT_KEY, list_2 (g, unit)))
  2933.         return hash_get_last();
  2934.     left = list_map (_mult, left_options (g));
  2935.     right = list_map (_mult, right_options (g));
  2936.     h = make (list_mapcomb (plus, left, unit_adder),
  2937.           list_mapcomb (plus, right, unit_neg_adder));
  2938.     list_free (left);
  2939.     list_free (right);
  2940.     hash_put (MULT_KEY, list_copy_2 (g, unit), h);
  2941.     return h;
  2942. }
  2943.  
  2944. static game_type aw (game_type g) {
  2945.     list_type left, right, l;
  2946.     game_type g0, h;
  2947.     int try;
  2948.  
  2949.     if (hash_test (AW_KEY, list_1 (g)))
  2950.         return hash_get_last();
  2951.     left = list_make();
  2952.     right = list_make();
  2953.  
  2954.     for (l = list_start (left_options (g)); l != NIL; l = list_rest (l))
  2955.         list_insert (left, minus (aw (list_pick (l)), two));
  2956.     for (l = list_start (right_options (g)); l != NIL; l = list_rest (l))
  2957.         list_insert (right, plus (aw (list_pick (l)), two));
  2958.     g0 = make (left, right);
  2959.     if (!is_int (g0)) {
  2960.         hash_put (AW_KEY, list_copy_1 (g), g0);
  2961.         return g0;
  2962.     } else if (gt (g, _rstar_)) {
  2963.         for (h = neg1, try = -1;;h = g_int (++try))
  2964.             if ((l = list_start (right_options (g))) != NIL) {
  2965.                 for (; l != NIL; l = list_rest (l))
  2966.                     if (ge (h, aw (list_pick (l)))) {
  2967.                         hash_put (AW_KEY, list_copy_1 (g), h = g_int (try+1));
  2968.                         return h;
  2969.                     }
  2970.             } else {
  2971.                 hash_put (AW_KEY, list_copy_1 (g), h = g_int (try+1));
  2972.                 return h;
  2973.             }
  2974.     } else if (lt (g, _rstar_)) {
  2975.         for (h = one, try = 1;; h = g_int (--try))
  2976.             if ((l = list_start (left_options (g))) != NIL) {
  2977.                 for (; l != NIL; l = list_rest (l))
  2978.                     if (le (h, aw (list_pick (l)))) {
  2979.                         hash_put (AW_KEY, list_copy_1 (g), h = g_int (try-1));
  2980.                         return h;
  2981.                     }
  2982.             } else {
  2983.                 hash_put (AW_KEY, list_copy_1 (g), h = g_int (try - 1));
  2984.                 return h;
  2985.             }
  2986.     } else {
  2987.         hash_put (AW_KEY, list_copy_1 (g), g0);
  2988.         return g0;
  2989.     }
  2990. }
  2991.  
  2992. game_type atomic_weight (game_type g) {
  2993.     _rstar_ = star (max_star (g) + 1);
  2994.     return aw (g);
  2995. }
  2996.  
  2997. list_type make_var (char *s) {
  2998.     int k;
  2999.     var_type v;
  3000.     
  3001.     v = list_make();
  3002.     for (k=0; *s!='\0'; s++, k++)
  3003.         list_insert (v, (k<<8) | *s);
  3004.     return v;
  3005. }
  3006.  
  3007. void set_var (var_type v, game_type g) {
  3008.     hash_delete (VAR_KEY, v);
  3009.     if (!list_equal (v, dummy_var)) {
  3010.         list_free (game_cell[g]->var);
  3011.         game_cell[g]->var = list_copy (v);
  3012.     }
  3013.     hash_put (VAR_KEY, v, g);
  3014. }
  3015.  
  3016. game_type get_var (var_type v) {
  3017.     if (hash_test (VAR_KEY, v)) return hash_get_last();
  3018.     else {
  3019.         myerror ("get_var: Variable not set.");
  3020.         return NO_GAME;
  3021.     }
  3022. }
  3023.  
  3024. unsigned long game_stat (void) {
  3025.     unsigned long n=0, t=0, v=0, nv=0;
  3026.     game_type g;
  3027.     game_cell_type l;
  3028.  
  3029.     for (g = 1; g <= game_cells; g++) {
  3030.         n = (n
  3031.              + (left_options (g) ? count_extended_left_options (g) + 1 : 0)
  3032.              + (right_options (g) ? count_extended_right_options (g) + 1 : 0));
  3033.         if (game_cell[g]->var != NIL) {
  3034.             nv++;
  3035.             v = v + list_length (game_cell[g]->var) + 1;
  3036.         }
  3037.     }
  3038.     t = list_length (unit_adder) + list_length (unit_neg_adder) + 2;
  3039.     printf ("game option lists: %u; mult lists: %u; variable lists: %u\n", n, t, v);
  3040.     printf ("variables: %u; ", nv);
  3041.     for (nv=0, l = game_free_list; l != GNIL; l = l->next) nv++;
  3042.     printf ("games: %u; total game cells: %u\n", game_cells, game_cells + nv);
  3043.     return n + t + v;
  3044. }
  3045.  
  3046. game_type zeros_vs (game_type g, int n)
  3047. {
  3048.     if (n == 0) return g;
  3049.     else if (n < 0) return negative (zeros_vs (g, -n));
  3050.     else return vs (zero, zeros_vs (g, n-1));
  3051. }
  3052. game_type vs_zeros(game_type g, int n) {return zeros_vs (negative (g), -(n));}
  3053. game_type vs(game_type g, game_type h) {return make (list_copy_1 (g), list_copy_1 (h));}
  3054. list_type left_options (game_type g) {return ko_value (g) || babyko_value (g) ? list_0 : game_cell[g]->left;}
  3055. list_type right_options(game_type g) {return ko_value (g) || babyko_value (g) ? list_0 : game_cell[g]->right;}
  3056.  
  3057. game_type on (game_type g, int n) {
  3058.     game_type h;
  3059.     
  3060.     if (! (count_left_options(g)==1 && count_right_options(g)==1)) {
  3061.         myerror ("on: Game not in correct form for on");
  3062.         return zero;
  3063.     }
  3064.     else if (n == 0) return zero;
  3065.     else if (n < 0) return negative (on (g, -n));
  3066.     else if (eq (nth_left_option (g, 1), zero)) {
  3067.         h = vs (on (g, n-1), nth_right_option (g, 1));
  3068.         if (!eq (h, plus (on (g, n-1), gexp (g, n))))
  3069.             myerror ("on: on and gexp didn't match");
  3070.         return h;
  3071.     } else if (eq (nth_right_option (g, 1), zero))
  3072.         return negative (on (negative (g), n));
  3073.     else {
  3074.         myerror ("on: Game not in correct form for on");
  3075.         return zero;
  3076.     }
  3077. }
  3078. game_type off (game_type g, int n) {return on (g, -n);}
  3079. game_type gexp (game_type g, int n) {
  3080.     game_type h;
  3081.     int i;
  3082.  
  3083.     if (! (count_left_options(g)==1 && count_right_options(g)==1)) {
  3084.         myerror ("gexp: Game not in correct form for gexp");
  3085.         return zero;
  3086.     }
  3087.     else if (n == 0) return zero;
  3088.     else if (n < 0) return negative (gexp (g, -n));
  3089.     else if (eq (nth_left_option (g, 1), zero)) {
  3090.         for (h = nth_right_option (g, 1), i=1; i<n; i++)
  3091.             h = minus (h, gexp (g, i));
  3092.         return vs (zero, h);
  3093.     } else if (eq (nth_right_option (g, 1), zero)) return negative (gexp (negative (g), n));
  3094.     else {
  3095.         myerror ("gexp: Game not in correct form for gexp");
  3096.         return zero;
  3097.     }
  3098. }
  3099. SHAR_EOF
  3100. fi
  3101. if test -f 'operations.h'
  3102. then
  3103.     echo shar: "will not over-write existing file 'operations.h'"
  3104. else
  3105. cat << \SHAR_EOF > 'operations.h'
  3106. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  3107.  
  3108. /* Basic definitions of games and operations on games, as in Winning
  3109.  * Ways (Berlekamp, Conway, Guy).  The functions for adding, negating
  3110.  * and comparing games are given here.  Most functions are "memoized",
  3111.  * meaning they first check if they have been called before with
  3112.  * the same arguments before executing.  Note that once you do a
  3113.  * make (left, right), both lists are no longer guaranteed to exist,
  3114.  * although the lists will be freed properly.  This is because
  3115.  * usually once you do a make, you typically only need to manipulate
  3116.  * the resulting game.
  3117.  */
  3118.  
  3119. /* Be careful about the list allocation and deallocation!  A good
  3120.  * sample function to look at is plus in operations.c.  Note in
  3121.  * particular the use of list_unordered_2 and list_copy_unordered_2
  3122.  * for hash table lookups.  list_unordered_2 is used ONLY for
  3123.  * temporary reference.  hash_put() needs to be given a list
  3124.  * it can keep.  In summary, the function which deallocate
  3125.  * a list automatically are list_1, list_2, ... (which never
  3126.  * really allocate a list to begin with), make, hash_put, vs,
  3127.  * and list_clobber.  Otherwise you should do a list_free.
  3128.  */
  3129.  
  3130. #define MAX_GAMES MAX_SIZE    /* Maximum number of games permitted */
  3131. #define GAME_BLOCK_SIZE 1000
  3132. #define NO_GAME ((game_type) 0)
  3133. #define CANONICAL_FLAG    (1<<0)
  3134. #define NUSB_FLAG    (1<<1)
  3135. #define HAS_KO_FLAG    (1<<4)
  3136. #define KO_FLAG        (1<<6)
  3137. #define KOBAR_FLAG    (1<<7)
  3138. #define BABYKO_FLAG    (1<<8)
  3139. #define BABYKOBAR_FLAG    (1<<9)
  3140. #define EVALUATED_FLAG (NUSB_FLAG|KO_FLAG|KOBAR_FLAG|BABYKO_FLAG|BABYKOBAR_FLAG)
  3141.  
  3142. typedef list_type var_type;
  3143.  
  3144. typedef struct game_struct {
  3145.     list_type left;
  3146.     list_type right;
  3147.     unsigned flags;
  3148.     Q_type Num;
  3149.     int Star;
  3150.     int Up;
  3151.     var_type var;            /* Variable pointing to g set by set_var */
  3152.     struct game_struct *next;
  3153. } *game_cell_type;
  3154.  
  3155. extern game_type    saltus;
  3156. extern int        period;
  3157. extern game_cell_type    game_cell[];    /* shouldn't really be externed -- for debugging */
  3158. extern game_type    zero;
  3159. extern game_type    one;
  3160. extern game_type    two;
  3161. extern game_type    neg1;
  3162. extern game_type    one_star;
  3163. extern game_type    ko;
  3164. extern game_type    kobar;
  3165. extern game_type    babyko;
  3166. extern game_type    babykobar;
  3167. extern char        *parser_input;
  3168. extern game_type    parser_output;
  3169. extern var_type        dummy_var;
  3170.  
  3171. extern void        init(void);
  3172. extern void        reinit(void);
  3173. extern void        clean(void);
  3174. extern game_type    make (list_type, list_type);
  3175. extern game_type    make_canonical (list_type, list_type);
  3176. extern game_type    zeros_vs (game_type, int);
  3177. extern game_type    vs_zeros (game_type, int);
  3178. extern game_type    vs (game_type, game_type);
  3179. extern list_type    left_options (game_type);
  3180. extern list_type    right_options (game_type);
  3181. /* #define's
  3182. extern unsigned        count_left_options (game_type);
  3183. extern unsigned        count_right_options (game_type);
  3184. extern game_type    nth_left_option (game_type, unsigned);
  3185. extern game_type    nth_right_option (game_type, unsigned);
  3186. */
  3187. extern boolean        is_canonical (game_type);
  3188. extern boolean        is_evaluated (game_type);
  3189. extern boolean        is_int (game_type);
  3190. extern boolean        is_num (game_type);
  3191. extern boolean        is_up (game_type);
  3192. extern boolean        is_star (game_type);
  3193. extern boolean        is_tiny (game_type);
  3194. extern boolean        is_miny (game_type);
  3195. extern boolean        is_on (game_type);
  3196. extern boolean        is_num_up_star (game_type);
  3197. extern boolean        is_num_star (game_type);
  3198. extern boolean        is_up_star (game_type);
  3199. extern boolean        is_int_ko_star (game_type);
  3200. extern boolean        is_int_ko (game_type);
  3201. extern boolean        is_num_up_star_babyko (game_type);
  3202. extern boolean        is_num_star_babyko (game_type);
  3203. extern boolean        is_num_babyko (game_type);
  3204. extern boolean        is_int_babyko (game_type);
  3205. extern boolean        has_ko (game_type);
  3206. extern char *        var_sprintn (char *, var_type, int);
  3207. extern boolean        is_var (game_type);
  3208.  
  3209. /* #define's
  3210. extern int        int_value (game_type);
  3211. extern Q_type        num_value (game_type);
  3212. extern int        star_value (game_type);
  3213. extern int        up_value (game_type);
  3214. */
  3215. extern game_type    tiny_value (game_type);
  3216. extern game_type    miny_value (game_type);
  3217. extern int        on_exponent (game_type);
  3218. extern game_type    on_value (game_type);
  3219. extern var_type        var_value (game_type);
  3220. extern int        ko_value (game_type);
  3221. extern int        babyko_value (game_type);
  3222. extern char *        var_sprint (char *, var_type);
  3223.  
  3224. extern game_type    plus (game_type, game_type);
  3225. extern game_type    negative (game_type);
  3226. extern game_type    minus (game_type, game_type);
  3227. extern game_type    times (int, game_type);
  3228.  
  3229. extern boolean        ge (game_type, game_type);    /* greater or equal */
  3230. extern boolean        le (game_type, game_type);    /* less than or equal */
  3231. extern boolean        eq (game_type, game_type);
  3232. extern boolean        gt (game_type, game_type);
  3233. extern boolean        lt (game_type, game_type);
  3234. extern char *        compare (game_type, game_type);
  3235. extern boolean        lmove_ok (game_type, game_type);
  3236. extern boolean        rmove_ok (game_type, game_type);
  3237.  
  3238. /* #define's
  3239. extern game_type    g_int (int);
  3240. extern game_type    num (Q_type);
  3241. extern game_type    star (int);
  3242. extern game_type    up (int);
  3243. extern game_type    down (int);
  3244. extern game_type    tiny (game_type);
  3245. extern game_type    miny (game_type);
  3246. */
  3247.  
  3248. extern Q_type        left_stop (game_type);
  3249. extern Q_type        right_stop (game_type);
  3250. extern list_type    incentives (game_type);
  3251. extern list_type    left_incentives (game_type);
  3252. extern list_type    right_incentives (game_type);
  3253.  
  3254. extern game_type    cool (game_type, Q_type);
  3255. extern Q_type        temperature (game_type);
  3256. extern game_type    freeze (game_type);
  3257. extern game_type    overheat (game_type, game_type, game_type);
  3258. extern game_type    heat (game_type, game_type);
  3259. extern game_type    mult (game_type, game_type);
  3260. extern Q_type        mean (game_type);
  3261. extern game_type    atomic_weight ( game_type);
  3262. extern game_type    on (game_type, int);
  3263. extern game_type    off (game_type, int);
  3264. extern game_type    gexp(game_type, int);
  3265.  
  3266. /* Variables names are encoded in lists to make use of hash routines */
  3267. extern var_type        make_var (char *);
  3268. extern void        set_var (var_type, game_type);
  3269. extern game_type    get_var (var_type);
  3270.  
  3271. extern game_type    int_ko_star (int, int, int);
  3272. extern game_type    int_babyko (int, int);
  3273. extern game_type    num_up_star_babyko (Q_type, int, int, int);
  3274.  
  3275. #define _flags(g) (game_cell[g]->flags)
  3276. #define extended_left_options(g) (game_cell[g]->left)
  3277. #define extended_right_options(g) (game_cell[g]->right)
  3278. #define count_left_options(g) list_length (left_options (g))
  3279. #define count_right_options(g) list_length (right_options (g))
  3280. #define count_extended_left_options(g) list_length (extended_left_options (g))
  3281. #define count_extended_right_options(g) list_length (extended_right_options (g))
  3282. #define nth_left_option(g,i) list_nth (left_options (g), i)
  3283. #define nth_right_option(g,i) list_nth (right_options (g), i)
  3284.  
  3285. #define num_value(g) (game_cell[g]->Num)
  3286. #define int_value(g) Q_p (num_value (g))
  3287. #define star_value(g) (game_cell[g]->Star)
  3288. #define up_value(g) (game_cell[g]->Up)
  3289.  
  3290. #define num_up_star(a,b,c) num_up_star_babyko (a,b,c,0)
  3291. #define num(n) num_up_star ((n), 0, 0)
  3292. #define g_int(n) num (Q_int (n))
  3293. #define star(n) num_up_star (Q_0, 0, (n))
  3294. #define up(n) num_up_star (Q_0, (n), 0)
  3295. #define down(n) negative (up (n))
  3296. #define tiny(g) vs (zero, vs (zero, negative (g)))
  3297. #define miny(g) vs (vs ((g), zero), zero)
  3298. #define set_flag(g,f) (game_cell[g]->flags |= (f))
  3299. #define clear_flag(g,f) (game_cell[g]->flags &= ~(f))
  3300.  
  3301. SHAR_EOF
  3302. fi
  3303. if test -f 'output.c'
  3304. then
  3305.     echo shar: "will not over-write existing file 'output.c'"
  3306. else
  3307. cat << \SHAR_EOF > 'output.c'
  3308. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  3309.  
  3310. /* WHOLE_TREE 1
  3311.    EVALUATED_TREE 2 */
  3312.  
  3313. #include <stdio.h>
  3314. #include "externs.h"
  3315. #include "rational.h"
  3316. #include "list.h"
  3317. #include "operations.h"
  3318. #include "output.h"
  3319.  
  3320. char            chill_string[MAXBUFF];
  3321. char            warm_string[MAXBUFF];
  3322. int expression (char *, game_type, int, boolean, boolean);
  3323.  
  3324. boolean is_print_simple (game_type g) {
  3325.     static char s[MAXBUFF];
  3326.     return !expression (s, g, MAXBUFF-1, FALSE, TRUE);
  3327. }
  3328.  
  3329. void game_print (game_type g) {
  3330.     static char s[MAXBUFF];
  3331.     printf ("%s", game_sprintn (s, g, MAXBUFF-1));
  3332.     return;
  3333. }
  3334.  
  3335. void game_printf (game_type g) {
  3336.     static char s[MAXBUFF];
  3337.     printf ("%s\n", game_sprintn (s, g, MAXBUFF-1));
  3338.     return;
  3339. }
  3340.  
  3341. char *game_sprint (char *s, game_type g) {
  3342.     return game_sprintn (s, g, MAXBUFF-1);
  3343. }
  3344.  
  3345. static char *strsub (s, old, new)
  3346.     char *s;
  3347.     char old, new;
  3348. {
  3349.     char *t;
  3350.     for (t=s; *t != '\0'; t++)
  3351.         if (*t == old) *t = new;
  3352.     return s;
  3353. }
  3354.  
  3355. static game_type warm(game_type g) {
  3356.     set_var (dummy_var = make_var (ARGUMENT_SYMBOL), g);
  3357.     strsub (warm_string, 'g', *ARGUMENT_SYMBOL);
  3358.     g = game_parse (warm_string);
  3359.     strsub (warm_string, *ARGUMENT_SYMBOL, 'g');
  3360.     return g;
  3361. }
  3362.  
  3363. static game_type chill (game_type g) {
  3364.     set_var (dummy_var = make_var (ARGUMENT_SYMBOL), g);
  3365.     strsub (chill_string, 'g', *ARGUMENT_SYMBOL);
  3366.     g = game_parse (chill_string);
  3367.     strsub (chill_string, *ARGUMENT_SYMBOL, 'g');
  3368.     return g;
  3369. }
  3370.  
  3371. #define appendg(g,t) expression (s + strlen (s), g, n - strlen (s), t, TRUE)
  3372. char *game_sprintn (char *s, game_type g, int n) {
  3373.     game_type chilled, warmed, frac, gnorm, small;
  3374.     Q_type k, k2;
  3375.     int t, norm;
  3376.     
  3377.     strcpy (s, "");
  3378.     if (g && (flags & EVALUATE_FLAG)) {
  3379.         k = mean (g);
  3380.         t=FALSE;
  3381.         if (Q_ge (k, 0)) {
  3382.             k2 = Q_plus (k, Q(1,2));
  3383.             norm = Q_p (k2) / Q_q(k2);
  3384.             if (Q_q (k2) == 1) norm--;
  3385.         }
  3386.         else {
  3387.             k2 = Q_minus (k, Q(1,2));
  3388.             norm = - ((- Q_p (k2)) / Q_q (k2));
  3389.             if (Q_q (k2) == 1) norm++;
  3390.         }
  3391.         if (!(flags & NORMALIZE_FLAG)) norm = 0;
  3392.         chilled = chill (minus (g, g_int (norm)));
  3393.         warmed = warm (chilled);
  3394.         frac = (has_ko (chilled) || !Q_eq (left_stop (chilled), right_stop (chilled)))
  3395.             ? zero : num (mean (chilled));
  3396.         small = minus (chilled, frac);
  3397.         if (   eq (g, plus (warmed, gnorm = g_int (norm)))
  3398.             || eq (g, plus (warmed, gnorm = plus (gnorm, star(1))))) {
  3399.             t = flags & EXPAND_FLAG;
  3400.             flags = (flags | EXPAND_FLAG) ^ EXPAND_FLAG;    /* clear flag */
  3401.             if (eq (chilled, zero))
  3402.                 appendg (gnorm, FALSE);
  3403.             else {
  3404.                 if (!eq (gnorm, zero)) appendg (gnorm, FALSE);
  3405.                 if (strlen (s) < n) strcat (s, flags & TEX_FLAG ? "\\int " : "%");
  3406.                 if (!eq (frac, zero)) appendg (frac, FALSE);
  3407.                 if (!eq (small, zero)) appendg (small, TRUE);
  3408.             }
  3409.             flags = flags | t;
  3410.         } else appendg (g, FALSE);
  3411.     } else appendg (g, FALSE);
  3412.     return s;
  3413. }
  3414.  
  3415. void list_print (list_type l) {
  3416.     static char s[MAXBUFF];
  3417.     printf ("%s", list_sprintn (s, l, MAXBUFF-1));
  3418.     return;
  3419. }
  3420.  
  3421. void list_printf (list_type l) {
  3422.     static char s[MAXBUFF];
  3423.     printf ("%s\n", list_sprintn (s, l, MAXBUFF-1));
  3424.     return;
  3425. }
  3426.  
  3427. char *list_sprint (char *s, list_type l) {
  3428.     return list_sprintn (s, l, MAXBUFF-1);
  3429. }
  3430.  
  3431. char *list_sprintn (char *s, list_type l, int n) {
  3432.     static char t[20];
  3433.  
  3434.     strncpy (s, "( ", n - strlen (s));
  3435.     while (l->next != NIL) {
  3436.         l = l->next;
  3437.         sprintf (t,"%d ", l->elt);
  3438.         strncat (s, t, n - strlen (s));
  3439.     }
  3440.     strncat (s, ")", n - strlen (s));
  3441.     return s;
  3442. }
  3443.  
  3444. #define ss(x) (strncat (s, (x), n - strlen (s)))
  3445. #define sd(x) (sprintf (buff, flags & TEX_FLAG ? " %d" : "%d", (x)), ss(buff))
  3446. #define sg(x) (expression (buff, (x), MAXBUFF-1, FALSE, FALSE), ss (buff))
  3447. #define sgp(x) (expression (buff, (x), MAXBUFF-1, TRUE, FALSE), ss (buff))
  3448. #define sv(x) (var_sprintn (s, var_value (x), n - strlen (s)))
  3449. #define TeX (flags & TEX_FLAG)
  3450. int expression (char *s, game_type g, int n, boolean brace, boolean attop) {
  3451.     char buff[MAXBUFF], left[MAXBUFF], right[MAXBUFF];
  3452.     int t, bars, lbars=0, rbars=0, i, ls, rs;
  3453.     Q_type m;
  3454.     game_type h;
  3455.  
  3456.     strcpy (s, "");
  3457.     h = minus (g, num (m = left_stop (g)));
  3458.     if (   ((is_tiny (h) || is_miny (h)) && (flags & TINYS_FLAG))
  3459.         || ((is_on (h)) && (flags & ONS_FLAG))
  3460.         || (is_num_up_star (g)
  3461.         && (Q_eq (num_value (g), Q_0)    || (flags & INTEGERS_FLAG))
  3462.         && (Q_is_int (num_value (g))    || (flags & NUMBERS_FLAG))
  3463.         && ((up_value (g) == 0)        || (flags & UPS_FLAG))
  3464.         && ((star_value (g) == 0)    || (flags & STARS_FLAG)))
  3465.         || (is_int_ko_star (g) && ko_value (g) != 0)
  3466.         || (is_num_up_star_babyko (g) && babyko_value (g) != 0)) {
  3467.         if (!Q_eq (m, Q_0) || eq (g, zero)) {
  3468.             if (TeX && Q_lt (m, Q_0)) ss ("\\neg"), m = Q_negative (m);
  3469.             if (Q_is_int (m)) sd (Q_p(m));
  3470.             else if (TeX) (ss ("{"), sd (Q_p(m)), ss ("\\over"), sd (Q_q(m)), ss ("}"));
  3471.             else (sd (Q_p(m)), ss ("/"), sd (Q_q(m)));
  3472.         }
  3473.         if ((t = up_value (g)) != 0)
  3474.             if (TeX) {
  3475.                 if (t == 2) ss ("\\Upup");
  3476.                 else if (t == -2) ss ("\\Downdown");
  3477.                 else if (t == 1) ss ("\\Up");
  3478.                 else if (t == -1) ss ("\\Down");
  3479.                 else ss (t>0? "\\UpN{" : "\\DownN{"), (t>1? sd (t) : t<-1? sd(-t) :0), ss("}");
  3480.             } else ss (t>0? "^" : "v"), (t>1? sd(t) : t<-1? sd(-t) :0);
  3481.         if ((ko_value (g)) == 1)  ss (TeX ? "\\Ko" : "K");
  3482.         if ((ko_value (g)) == -1) ss (TeX ? "\\Kobar" : "-K");
  3483.         if ((t = star_value (g)) > 0) (ss (TeX?"\\Star":"*"), t>1? sd (t) :0);
  3484.         if (is_tiny (h)) ss (TeX?"\\Tiny{":"+["), sg (tiny_value (h)), ss (TeX?"}":"]");
  3485.         if (is_miny (h)) ss (TeX?"\\Miny{":"-["), sg (miny_value (h)), ss (TeX?"}":"]");
  3486.         if (is_on (h)) sgp (on_value (h)), ss (TeX?"^{\\to ":"<("), sd (on_exponent (h)), ss (TeX?"}":")>");
  3487.         if ((babyko_value (g)) == 1)  ss (TeX ? "\\ko" : "k");
  3488.         if ((babyko_value (g)) == -1) ss (TeX ? "\\kobar" : "-k");
  3489.         return 0;
  3490.     } else if ((flags & VARS_FLAG) && is_var (g)) {
  3491.         sv (g);
  3492.         if (attop && (flags & EXPAND_FLAG)) ss (" = ");
  3493.         else return 0;
  3494.     }
  3495.     /*********** At this point we're looking at a Gl|Gr or {Gl|Gr} **********/
  3496.     ls = count_left_options (g);
  3497.     rs = count_right_options (g);
  3498.     *left = *right = '\0';
  3499.     if (ls == 0 || rs == 0) brace = TRUE;
  3500.     for (i = 1; i <= ls; i++) {
  3501.         t = expression (buff, nth_left_option (g, i), MAXBUFF-2, ls > 1, FALSE);
  3502.         if (i < ls) strcat (buff, ",");
  3503.         lbars = (t > lbars) ? t : lbars;
  3504.         strncat (left, buff, MAXBUFF-1 - strlen (left));
  3505.     }
  3506.     for (i = 1; i <= rs; i++) {
  3507.         t = expression (buff, nth_right_option (g, i), MAXBUFF-2, rs > 1, FALSE);
  3508.         if (i < rs) strcat (buff, ",");
  3509.         rbars = (t > rbars) ? t : rbars;
  3510.         strncat (right, buff, MAXBUFF-1 - strlen (right));
  3511.     }
  3512.     lbars++;
  3513.     rbars++;
  3514. #define E_LBRACE (ss (TeX?"\\{":"{"))
  3515. #define E_RBRACE (ss (TeX?"\\}":"}"))
  3516. #define E_BAR (ss (TeX?"|":"|"))
  3517.     bars = (lbars > MAXBARS ? rbars :
  3518.         rbars > MAXBARS ? lbars :
  3519.         lbars > rbars ? lbars : rbars);
  3520.     if (brace) E_LBRACE;
  3521.     if (lbars > MAXBARS) E_LBRACE;
  3522.     ss (left);
  3523.     if (lbars > MAXBARS) E_RBRACE;
  3524.     if (bars > MAXBARS) E_BAR;
  3525.     else for (i = 1; i <= bars; i++) E_BAR;
  3526.     if (rbars > MAXBARS) E_LBRACE;
  3527.     ss (right);
  3528.     if (rbars > MAXBARS) E_RBRACE;
  3529.     if (brace) E_RBRACE;
  3530.     return (brace ? 0 : bars > MAXBARS ? 1 : bars);
  3531. }
  3532. SHAR_EOF
  3533. fi
  3534. if test -f 'output.h'
  3535. then
  3536.     echo shar: "will not over-write existing file 'output.h'"
  3537. else
  3538. cat << \SHAR_EOF > 'output.h'
  3539. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  3540.  
  3541. /* Output routines for games:  expressions and trees */
  3542. /* Note: I assume sprintf returns length of string */
  3543.  
  3544. #define MAXBARS 3
  3545.  
  3546. extern char        chill_string[MAXBUFF];
  3547. extern char        warm_string[MAXBUFF];
  3548.  
  3549. extern boolean        is_print_simple (game_type);
  3550. extern void        game_print (game_type);
  3551. extern void        game_printf (game_type);
  3552. extern char *        game_sprint (char *, game_type);
  3553. extern char *        game_sprintn (char *, game_type, int);
  3554. extern void        list_print (list_type);
  3555. extern void        list_printf (list_type);
  3556. extern char *        list_sprint (char *, list_type);
  3557. extern char *        list_sprintn (char *, list_type, int);
  3558. /* extern char *    tree (char *, game_type, int, int); (not yet written)*/
  3559. /* extern char *    var_sprint (char *, var_type);
  3560.  *   lies in  operations.h */
  3561.  
  3562. SHAR_EOF
  3563. fi
  3564. if test -f 'parse.l'
  3565. then
  3566.     echo shar: "will not over-write existing file 'parse.l'"
  3567. else
  3568. cat << \SHAR_EOF > 'parse.l'
  3569. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  3570. /* Includes mostly code written by David Moews */
  3571.  
  3572. %%
  3573. stat                        {return STAT;}
  3574. freeze                        {return FREEZE;}
  3575. chill[\n]                    {printf ("%s", chill_string); return ENDOFSTRING;}
  3576. warm[\n]                    {printf ("%s", warm_string);  return ENDOFSTRING;}
  3577. chill[^\n]*[\n]                    {strcpy (chill_string, yytext+5); return ENDOFSTRING;}
  3578. warm[^\n]*[\n]                    {strcpy (warm_string, yytext+5); return ENDOFSTRING;}
  3579. on                        {return ON;}
  3580. off                        {return OFF;}
  3581. mean                        {return MEAN;}
  3582. temperature                    {return TEMPERATURE;}
  3583. temp                        {return TEMPERATURE;}
  3584. aw                        {return AW;}
  3585. integers                    {return INTEGERS;}
  3586. numbers                        {return NUMBERS;}
  3587. stars                        {return STARS;}
  3588. ups                        {return UPS;}
  3589. tinys                        {return TINYS;}
  3590. tinies                        {return TINYS;}
  3591. ons                        {return ONS;}
  3592. variables                    {return VARS;}
  3593. expand                        {return EXPAND;}
  3594. all                        {return ALL;}
  3595. prompt                        {return PROMPT;}
  3596. evaluate                    {return EVALUATE;}
  3597. eval                        {return EVALUATE;}
  3598. normalize                    {return NORMALIZE;}
  3599. normal                        {return NORMALIZE;}
  3600. norm                        {return NORMALIZE;}
  3601. echo                        {return ECHO_;}
  3602. assume                        {return ASSUME;}
  3603. assume2                        {return ASSUME2;}
  3604. reset                        {return RESET;}
  3605. clean                        {return CLEAN;}
  3606. tex                        {return TEX;}
  3607. no                        {return NO;}
  3608. help                        {return HELP;}
  3609. corridor                    {return CORRIDOR;}
  3610. corr                        {return CORRIDOR;}
  3611. cor                        {return CORRIDOR;}
  3612. domineering                    {return DOMINO;}
  3613. domineer                    {return DOMINO;}
  3614. domino                        {return DOMINO;}
  3615. dom                        {return DOMINO;}
  3616. saltus                        {return SALTUS;}
  3617. period                        {return PERIOD;}
  3618. "|"                        {return BAR;}
  3619. "||"                        {return BARR;}
  3620. "|||"                        {return BARRR;}
  3621. "||||"                        {return BARRRR;}
  3622. "|||||"                        {return BARRRRR;}
  3623. "|0<"[0-9]+">"                    {extern int atoi();
  3624.                          yylval.ival = atoi(yytext+3);
  3625.                          return BARZEROS;}
  3626. 0"<"0-9]+">"                        {extern int atoi();
  3627.                          yylval.ival = atoi(yytext+2);
  3628.                          return ZEROS;}
  3629. 0|[1-9][0-9]*                    {extern int atoi();
  3630.                          yylval.ival = atoi(yytext);
  3631.                          return NUM;}
  3632. "<("[1-9][0-9]*")>"                {extern int atoi();
  3633.                          yylval.ival = atoi(yytext+2);
  3634.                          return ONNUM;}
  3635. [<>%_?\+\(\)\{\}\[\]\.\-\^\*v,\/=Kk]        {return *yytext;}
  3636. "-K"                        {return MINUS_K;}
  3637. "-k"                        {return MINUS_k;}
  3638. "+"/"["                        {return TINY;}
  3639. "-"/"["                        {return MINY;}
  3640. [\n]                        {return ENDOFSTRING;}
  3641. [ \t]                        {}
  3642. [bu]/[0-9]                    {return *yytext;}
  3643. v*['\1'$a-uw-zA-Z][a-zA-Z]*[0-9]*        {yylval.lval = make_var (yytext);
  3644.                          return S;}
  3645. .                        {return UNKNOWN;}
  3646. %%
  3647. int yywrap()
  3648. {
  3649.     return 1;
  3650. }
  3651.  
  3652. #define my_getc() (*(parser_input++))
  3653. #undef input
  3654. # define input() (((yytchar=yysptr>yysbuf?U(*--yysptr):my_getc())==10?(yylineno++,yytchar):yytchar)==EOF?0:yytchar)
  3655.  
  3656. char *strdup (s)
  3657.     char *s;
  3658. {
  3659.     char *t, *malloc();
  3660.     t = malloc (strlen (s) + 1);
  3661.     strcpy (t, s);
  3662.     return t;
  3663. }
  3664. SHAR_EOF
  3665. fi
  3666. if test -f 'rational.c'
  3667. then
  3668.     echo shar: "will not over-write existing file 'rational.c'"
  3669. else
  3670. cat << \SHAR_EOF > 'rational.c'
  3671. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  3672.  
  3673. #include "externs.h"
  3674. #include "rational.h"
  3675.  
  3676. #define p(x) Q_p(x)
  3677. #define q(x) Q_q(x)
  3678.  
  3679. int Q_error=FALSE;
  3680.  
  3681. int _Q_to_int (Q_type x) {        /* Cast Q_type into int, keeping low order bits */
  3682.     int i,y;
  3683.     for (i=y=0; i<INT_SIZE; i++, x>>=1)
  3684.         if (x & Q_BIT) y|=(1<<i);
  3685.     return y;
  3686. }
  3687.  
  3688. Q_type _int_to_Q (int x) {
  3689.     int i;
  3690.     Q_type y=Q_0;
  3691.     for (i=0; i<INT_SIZE; i++, x>>=1)
  3692.         if (x & 1) y |= (Q_BIT<<i);
  3693.     return y;
  3694. }
  3695.  
  3696. int Q_q (Q_type x) {
  3697.     int q = 1;
  3698.     while (!Q_is_int (x)) x <<= 1, q <<= 1;
  3699.     return q;
  3700. }    
  3701. /*    return (Q_is_int (x)) ? 1       OLD CODE
  3702.         : Q_to_int (Q_1 / (((x ^ (x-Q_BIT)) + Q_BIT) >> 1));
  3703. */
  3704.  
  3705. int Q_p (Q_type x) {
  3706.     return Q_to_int (Q_is_int (x) ? x >> Q_SHIFT
  3707.              : x / (((x ^ (x-Q_BIT)) + Q_BIT) >> 1));
  3708. }
  3709.  
  3710. Q_type Q_times (Q_type x, Q_type y) {
  3711.     return Q (p(x)*p(y), q(x)*q(y));
  3712. }
  3713.  
  3714. Q_type Q_divide (Q_type x, Q_type y) {
  3715.     if (p(y) == 0) myerror ("Q_divide: divide by zero");
  3716.     else if (y == Q_2) return x>>1;
  3717.     return Q (p(x)*q(y), q(x)*p(y));
  3718. }
  3719.  
  3720. Q_type Q_simplest_number (Q_type x, Q_type y) {
  3721.     int i;
  3722.     Q_type z;
  3723.     if (Q_ge (x, y)) {
  3724.         myerror ("Q_simplest_number: first argument exceeds second");
  3725.         return Q_0;
  3726.     }
  3727.     else if (Q_lt (x, Q_0)) return Q_gt (y, Q_0) ? Q_0
  3728.         : Q_negative (Q_simplest_number (Q_negative (y), Q_negative (x)));
  3729.     else if (Q_lt (Q_int(p(x)/q(x) + 1), y)) return Q_int(p(x)/q(x) + 1);
  3730.     for (i=1; (x>>i) != (y>>i); i++);
  3731.     i--;
  3732.     z = ((x >> i) << i);
  3733.     if ((z | (Q_BIT<<i)) < y) z |= (Q_BIT << i);
  3734.     else while (z <= x && i >= 0) z |= (Q_BIT << --i);
  3735.     if (!(x < z && z < y)) myerror ("Q_simplest_number: rational fucked up");
  3736.     return z;
  3737. }
  3738.  
  3739. void Q_printf (Q_type x) {
  3740.     printf ("%d/%d\n", Q_p(x), Q_q(x));
  3741.     return;
  3742. }
  3743. SHAR_EOF
  3744. fi
  3745. if test -f 'rational.h'
  3746. then
  3747.     echo shar: "will not over-write existing file 'rational.h'"
  3748. else
  3749. cat << \SHAR_EOF > 'rational.h'
  3750. /* Copyright (C) David Wolfe, 1990.  All rights reserved. */
  3751.  
  3752. /* Does arithmetic on dyadic rationals. */
  3753.  
  3754. typedef long Q_type;
  3755. extern int Q_error;
  3756. #define Q_SIZE 32
  3757. #define Q_SHIFT 20
  3758. #define Q_BIT ((Q_type) 1)
  3759.  
  3760. #define Q_0 ((Q_type) 0)
  3761. #define Q_1 (Q_BIT << Q_SHIFT)
  3762. #define Q_2 (Q_1 << 1)
  3763. #define Q_neg1 (- Q_1)
  3764. #define Q_infinity (((( Q_BIT << (Q_SIZE-2)) - Q_BIT) << 1) + Q_BIT)
  3765.  
  3766. /* Internal use only: don't use these */
  3767. #if (Q_SIZE > INT_SIZE) & !defined(IBMPC)
  3768. extern int        _Q_to_int(Q_type);
  3769. extern Q_type        _int_to_Q(int);
  3770. #define Q_to_int _Q_to_int
  3771. #define int_to_Q _int_to_Q
  3772. #else
  3773. #define Q_to_int(x) ((int) x)
  3774. #define int_to_Q(x) ((Q_type) x)
  3775. #endif
  3776.  
  3777. #define Q(a,b)        (int_to_Q(a) * (Q_1 / ((Q_type) b)))
  3778. #define Q_int(a)    (int_to_Q(a) << Q_SHIFT)
  3779. #define Q_plus(x,y)    ((x)+(y))
  3780. #define Q_negative(x)    (-(x))
  3781. #define Q_minus(x,y)    ((x)-(y))
  3782. #define Q_ge(x,y)    ((x) >= (y))
  3783. #define Q_le(x,y)    ((x) <= (y))
  3784. #define Q_eq(x,y)    ((x) == (y))
  3785. #define Q_gt(x,y)    ((x) > (y))
  3786. #define Q_lt(x,y)    ((x) < (y))
  3787. #define Q_is_int(x)    ((x & (Q_1 - Q_BIT)) == Q_0)
  3788. #define Q_exp(a)    (Q_BIT << (Q_SHIFT + a))
  3789. #define Q_sprint(s,x)    sprintf (s, "%d/%d", Q_p(x), Q_q(x))
  3790.  
  3791. extern int        Q_p (Q_type);
  3792. extern int        Q_q (Q_type);
  3793. extern Q_type        Q_times (Q_type, Q_type);
  3794. extern Q_type        Q_divide (Q_type, Q_type);
  3795. extern Q_type        Q_simplest_number (Q_type, Q_type);
  3796. extern void        Q_printf (Q_type);
  3797. SHAR_EOF
  3798. fi
  3799. exit 0
  3800. #    End of shell archive
  3801.